ABC171参加してました。今回は43分で4完できたのでめっちゃ喜んでいました。パフォーマンスも上がりました。やったね！ただ、今までのマイナスが大きすぎてハイスコアすら更新できない辛さ。年内には緑に上がりたいです。
ateruimashinさんのAtCoder Beginner Contest 171での成績：4289位
パフォーマンス：779相当
レーティング：468→506 (+38) 🙂#AtCoder #ABC171 https://t.co/CWS0SVUXUY
来週も緑目指してがんばります。— やーご (@ateruimashin) June 21, 2020
目次
1.A問題
やるだけです。char型の比較では、文字と文字を比較できることを忘れなければif文だけで実装できました。私はASCIIコード表出さなきゃ！って慌ててました。
2.B問題
これもやるだけです。価格を昇順にソートして、先頭からN個加算すれば終わりです。
3.C問題
問題文見て計算用紙に書き出してから、なんだこれ・・・？となってD問題を通した後に解きました。実装してみたらただそれだけって感じでした。
要するに26進数表記のi桁目の文字がそのまま出力すべき文字列のi番目と一致します。なので、与えられた整数nを26で割った余りを出して、それを文字に変換して、その後、nを26で割ってみたいなことを繰り返すと良さげでした。
余りを出す前にn-1することを忘れないようにしましょう。
私の実装だと、後ろの文字から決まっていくので、reverseを掛けてちゃんとした順番にしています。
また、今回数値→文字は26進数で0がa,1がbに対応するようになっているので、そうなるように実装しています。今回のコンテストはchar周りの出題多めですね。
4.D問題
C問題より先に解けた問題。解けたときは「いける・・・いけるぞ！！」となりました。
ぶっちゃけこれもやるだけといえばやるだけです。
数列内の各数字のカウントだけやって、その数字のカウント分配列の合計値からbを引いてあげて、cを足してあげます。その後、配列内のbと一致する数字のカウントを0にして、cと一致する数字のカウントにbを足します。これを繰り返すと通りました。
この日の朝にハッシュテーブルなるものを扱った問題を解いていたので、「ハッシュテーブルつかったるか！！」と思ってハッシュテーブルで実装しています。後で考えたら配列でもよかったです。ハッシュテーブルを使ってもやってることは同じです。最初書いた時、配列の最大値を更新するのを忘れていて、入力例1で躓いていました。
5.E問題
暗号学を研究している端くれとして、XOR系の問題は通したいと思いましたが、全く思いつかず断念しました。しかし解説を読めばすぐに理解できました。
数学の問題かなと思います。重要なのは、与えられる配列の要素の全ての排他的論理和を取ったものと、出力すべき各要素の全ての排他的論理和を取ったものは等しいという点。ここでNが偶数であることが必要です。もしNが奇数なら排他的論理和を取った後の結果は0になります。
このすべての要素の排他的論理和をSとすると、任意のaに対するbは、Sとaの排他的論理和を取ったものになります。
この問題で最も重要な排他的論理和を性質は、同じ数字の排他的論理和は0であるという点だと思います。この性質を生かして考察すれば解けたかも・・・？
排他的論理和を調べていると、C言語ならa^bで排他的論理和を計算できるそうですが、C++でそれを書くとダメでした。
代わりに^=を使うとうまくいきました。std::bitsetを使わないとダメらしいです。
参考:cpprefjp – C++日本語レファレンス std::bitset
6.おわりに
F問題は無理そうだなと思って諦めました。
とりあえず、4完できたことはとても嬉しいです。しかし、E問題は暗号学の研究をしている学生の端くれとしては悔しいなと思います。
いま、やっとAtCoder ProblemsのBoot camp for BeginnersのMediumが半分を超えました。ABCのC問題を中心に解いていますが、1問にかかるスピードがEasyと比べ物にならないぐらい遅い。しかし、いろいろなことを学べるので、頑張ってMediumを終わらせます。