AtCoder Beginner Contest 137

結果

順位   462nd / 5218
パフォーマンス   1685
レーティング  1906 → 1885(-21)

　D問題までの4問しか解けなくてひえーって感じだったけど失敗に優しいAtCoderなので。

C - Green Bin

　各文字列について各26文字の出現回数を記録したstd::vectorをstd::mapに詰めていく。こういうSTLにSTLを突っ込むみたいなSTLを信じ切った解法だと内部的な振る舞い（メモリがどうなっているのかとか）がさっぱり想像できなくて不安だけどできるものはできる。

　提出

D - Summer Vacation

　 $M - i$ 日目には遅延が $i$ 日以内のものから最大のものを選びたくなった。報酬の遅延日数で昇順ソートして、std::priority_queueに詰めながらやっていくと通る。ここまでは結構順調に解けていたのだが……。

　提出

E - Coins Respawn

　85分ずっとこの問題に取り組んで結局解けず。原因は簡単で、ベルマンフォード法とワーシャルフロイド法が頭の中で混じってしまい、ベルマンフォード法は $O(|V|^3)$ だからダメだよなぁと早々に切ってしまったから。ダイクストラを適当にいじってなんとかする方針でずっと考えてハマり続ける展開になってしまってはもうダメ。

　こういう勘違いを、コンテスト中の振る舞いを変えることで回避することができるのかよくわからない。頭の中だけで切らず文章として残そうとすれば気づけただろうか。しかし「メモを丁寧に取ろう」みたいな心がけに頼ってなんとかしようとするのはどうせ数回でまたもとに戻ってしまうと経験上わかっているので良くない。メモを取るのが嫌な理由として紙にペンで文字を書くのが遅いという点はあるし、パソコンで書くのはありかもしれない。グラフとか図とかは書きづらいので思考部分のみにはなりそうだけど。

　あとはもっとWeb検索を用いたほうがいい。今回詰まっている間は一回も検索してなくて、コンテスト終わった後にふと「負の閉路」で調べてベルマンフォード法をちらっと見ただけであーこれは……という感じになったので。基本的に自分の頭で考えてなんとかなることはそんなに多くない。

　まぁコンテスト中の振る舞いというよりは、どちらかというとアルゴリズムの知識があやふやだった、訓練不足だったというところが大きいとは思う。あまり競技プログラミングをがっつりやっていくという気分ではないのでこうやってコンテストでやらかして覚えるということになっていくのだろうけど。

　提出