ABC171振り返り

ABC171の振り返りをします。

結果は47分A-E5完1ペナでレートが少しだけ上がりました。

Eが多くの人に解かれていてびっくりしました。
F問題が解けなくて残念すぎました。

コンテスト中

A問題

A - 留lphabet

大文字かどうかを判定するisupper関数があったみたいです。
それを利用すると以下のようにかけます。

int main(){
 char s; cin >> s;
 if(isupper(s)) cout << "A" << endl;
 else cout << "a" << endl;
}

その存在を知らなかったので文字コードを利用して書きました。（クリックすれば出典元に飛べます。）

よく桁DPでも行う処理です。

int main(){
 char c; cin >> c;
 ll a = c - 'a';
 // cout << a << endl;
 if(a >= 0) cout << "a" << endl;
 else cout << "A" << endl;
}

文字コードの処理に関して理解が甘かったこともわかりました。
以下のような挙動をします。

int main(){
 cout << typeid('a' + 1).name() << endl;
 // i (intを示す)が出力
 char s; s = 'a' + 1;
 cout << typeid(s).name() << " " << s << endl;
 // c(charを示す) , b が出力
 ll a; a = 'a' + 1;
 cout << typeid(a).name() << " " << a << endl;
 // x(long longを示す), 98 が出力

 s = 65;
 cout << s << endl;
 // Aが出力
}

B問題

B - Mix Juice

合計の価格を小さくしたいので、小さいものから選んでいけば良いです。
ソートしてから前のK個を足します。

int main(){
 ll N , K; cin >> N >> K;
 vector<ll> p(N); rep(i,N) cin >> p[i];

 SORT(p);
 ll ans = 0;
 rep(i,K){
   ans += p[i];
 }
 cout << ans << endl;
}

C問題

C - One Quadrillion and One Dalmatians

文字列を出力するのは意外と用心が必要な印象です。
コンテスト中の提出では、文字列の長さを求めてからそれぞれの文字を求めていきました。

長くなってしまったので提出を載せておきます。

Submission #14552766 - AtCoder Beginner Contest 171

もっと簡潔にNを変化させながら文字列を求めることができました。
26で割った数字とあまりを考えながらNを減少させていきます。

int main(){
 ll N; cin >> N;
 string ans;
 while(N){
   N--;
   ans.pb('a' +  N % 26);
   N /= 26;
 }
 reverse(ans.begin() , ans.end());
 cout << ans << endl;
}

文字数がnの時に番号は26^nになるので、N = 10^15程度ならば文字列は15で余裕で抑えられ、十分高速に計算可能であることはわかりながらかけました。

D問題

D - Replacing

ある要素を順番に書き換える際の合計値を求める問題です。

それぞれの数が何個あるかという情報が大事なのでmapを利用してかけました。

int main(){
 ll N; cin >> N;
 vector<ll> a(N); rep(i,N) cin >> a[i];
 ll Q; cin >> Q;
 vector<ll> b(Q); vector<ll> c(Q);
 rep(i,Q) cin >> b[i] >> c[i];

 ll ans = 0; rep(i,N) ans += a[i];
 map<ll ,ll> m;
 rep(i,N) m[a[i]]++;

 rep(i,Q){
   if(m[b[i]] > 0){
     // 変更あり
     ans += (c[i] - b[i]) * m[b[i]];
     m[c[i]] += m[b[i]];
     m[b[i]] = 0;
   }
   cout << ans << endl;
 }
}

E問題

E - Red Scarf

Nが偶数だということを強調してくれています。
ベクトルaの要素が、自分以外の数字のxorであるという問題です。

a + b = 10
b + c = 9
a + c = 12

みたいな問題を思い出しました。

同じ数を偶数回xorの演算をすると0になることを利用することに気づけました。

ベクトルaの全ての要素をxorした数字はそれぞれの数字を奇数回xorした数字なので、その数字にそれぞれのa_iとxorの処理をすることで、自分の数字のみが残ります。

int main(){
 ll N; cin >> N;
 vector<ll> a(N); rep(i,N) cin >> a[i];

 ll t = 0;
 rep(i,N){
   t = t ^ a[i];
 }

 vector<ll> ans(N);
 rep(i,N){
   ans[i] = t ^ a[i];
   cout << ans[i] << " ";
 }
 cout << endl;
}

コンテスト後

F問題

F - Strivore

解説がとてもわかりやすかったです。

形式的べき級数の考え方も少しは理解できたのですが、自分にはまだコンテスト中にその考え方を利用するほど習得できていません。

この問題とはそこまで関係はないかもしれませんが、以前Twitterでみたこんな問題を思い出しました。

正解は、１の「奇数、奇数、偶数」です。

「奇数、奇数、偶数」：「奇数、偶数、奇数」の割合はどのくらいでしょうか？という問題の方が面白かったかなあ(；´∀｀) pic.twitter.com/DWYvGkbOGA

— みゆ@ますらば (@dqx_miyu) December 22, 2019

完成した後の文字列の数について考えます。
元々ある文字列の長さをNとします。
元ある文字列の前後に文字を入れていけるのですが、元ある文字の後ろの文字には被らないように文字を挿入していくという制約で考えることで、完成後の文字列を重複しないで数えることができます。

この発想さえできてしまえば、最後の文字の後にいれる文字数iに対して、それぞれの文字の間にいれるの文字数の選び方が、重複組み合わせの考え方でchoose(K - i + N - 1 , N - 1)と計算できることを利用してACできました。

int main() {
   // 前処理
   COMinit();
   ll K; cin >> K;
   string s; cin >> s;
   ll N = s.size();

   ll ans = 0;
   rep(i,K + 1){
     // i文字が最後の自由な文字の数
     ans += modpow(25, K - i , MOD) * COM(K - i + N - 1 , N - 1)
     % MOD * modpow(26 , i , MOD) % MOD;
     ans %= MOD;
   }
   cout << ans << endl;
}

こういう問題は得意な気もするけど、得意じゃないのかもしれない(´ω`)