ABC200です。レーティング-15でした。やはりA~Cの早解きが緑への近道かあと思っています。そんなわけでA~D問題の復習です。E問題はいろいろな解法があるようですが、私はその議論に参加できるほど強くないので、強くなって出直してきます。
目次
1.A問題
100で割って1足すと西暦が世紀になります。注意すべきは西暦が100の倍数の時は1を足さないことです。
2.B問題
書かれているとおりにやるだけ問題。数値の後ろに数字を付け足す(文字列としてみたら結合)ところがネック。いちいち数値⇔文字列をやるのはめんどくさいので、結合する場合は元の数値を1000倍して200を足せば同じことができます。
3.C問題
C – Ringo's Favorite Numbers 2
危うく死にかけた問題。通せたのでレーティングの減少が15で済んだ。通せてなかったら・・・考えたくないね。
やることはバケットソートをして、数列の先頭から、その数字に対応するバケツ内の個数-1を答えに足し続けるだけです。
4.D問題
鳩の巣原理によって探索する区間を絞ることができるらしい。
鳩の巣原理(問題名は誕生日のパラドックスから?)はN羽の鳩をM個の巣に分ける時、N>Mであれば少なくとも1個の巣には2羽以上の鳩がいるという原理です。
今回の問題の場合、取りうる数列は通りですが、その数列の和を200で割った余りは200通りに分類できます。そのため、であるならば、鳩の巣原理を適用すると、個の数列を200通りの余りに分類するため、少なくとも和の余りが同じになる数列が2つ存在することになります。
よって、数列の長さは最大200ですが、その中から適当に8つ取り出して和の余りが一致する数列を探せばいい(全探索)となります。
解説を読んだ時、なんて頭のいい解法なんだ！！と思いました。全探索っぽいけど最大の数列を全探索したら確実にTLEだから、DPか？と思ってググってましたが、こうやって探索範囲を絞れるとは驚きです。
研究室で暗号学的ハッシュ関数をやってた時期もあったので、誕生日のパラドックスは知ってたのですが、競技プログラミングでこういう形で出てくるとは。
twitter見ていると、強い人には典型だったらしいので覚えておこう。
5.おわりに
レート-15でしたが、楽しいコンテストでした。Cはもっと早く通すべきでした。
このコンテストの前に過去問をやっていて、ABCの茶色の問題は全て解き終わりました。ただ、緑になるためにはA~C問題の早解きが重要なのでどう練習すればいいんだろう？と思っています。もう一度C問題を解き直して分類するのは手間だし・・・。
とりあえずいい加減解法集はつくらないとなあ。そういえば強い人が典型問題コンテストやってるし、それをやるのもありか。
どうでもいいですが、VScodeのエディタからターミナルへフォーカスするショートカットキー、Shift+0は辞めたほうがいいです。めっちゃ誤爆します。