ABC200復習

投稿者: | 2021年5月9日
abc200

ABC200です。レーティング-15でした。やはりA~Cの早解きが緑への近道かあと思っています。そんなわけでA~D問題の復習です。E問題はいろいろな解法があるようですが、私はその議論に参加できるほど強くないので、強くなって出直してきます。

1.A問題

A – Century

100で割って1足すと西暦が世紀になります。注意すべきは西暦が100の倍数の時は1を足さないことです。

2.B問題

B – 200th ABC-200

書かれているとおりにやるだけ問題。数値の後ろに数字を付け足す(文字列としてみたら結合)ところがネック。いちいち数値⇔文字列をやるのはめんどくさいので、結合する場合は元の数値を1000倍して200を足せば同じことができます。

3.C問題

C – Ringo's Favorite Numbers 2

危うく死にかけた問題。通せたのでレーティングの減少が15で済んだ。通せてなかったら・・・考えたくないね。

やることはバケットソートをして、数列の先頭から、その数字に対応するバケツ内の個数-1を答えに足し続けるだけです。

4.D問題

D – Happy Birthday! 2

鳩の巣原理によって探索する区間を絞ることができるらしい。

鳩の巣原理(問題名は誕生日のパラドックスから?)は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は辞めたほうがいいです。めっちゃ誤爆します。

6.参考文献

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください