SRM 526

初の2連続2完で満足度高い。2完勢の中では最下位に近いけどそれはまだ気にしないことにする。2完してレートが下がるようになったら真剣に考えよう。今回の問題はEasyの方が難しかったような。Mediumはちょっと典型的だったような気がする。以下コンテストの流れ。
今回も割り当て遅いなーと思いながら待機。Twitter上ではログインできないとかの不穏な情報もチラチラ。コンテスト開始時刻になってもしばらく開かずに焦る。その後少し遅延して始まったけどコーディングフェーズはちゃんと75分確保されてるしratedになると信じて気合を入れて取り組む。
まず250を開いて、問題文をほとんど読まずにsample1,2から推測して超簡単な全探索だと思って書き上げた。ところが誤読だったらしい。書き直す。まだ誤読だったらしい。問題文を正しく理解したらこれ結構難しい。最小費用流が頭をよぎったけどさすがにアレなのでもっと書きやすい方法を考える。何とか全探索+greedyっぽいので行けそうだったので書いたらサンプル通った。この時点で時間を大量消費していたのでさっさと提出して500へ向かった。
500を開く前にDivision Summaryで順位が良くないことを確認して気合を入れ直す。問題文を読むと最短手数勝ちを目指すゲーム木探索が見える。サンプルよく読むと自分の解釈と一致しない。不穏な空気を感じて問題文を読み直すとまた誤読していた。定石通りの組み方を普通にやると計算量が微妙に大きい。でもRMQで計算量落ちることがすぐ分かったので書き始めた。書いて実行したらRE起こす。gdb使って色々調べたけど局所変数大きすぎてstack overflowしていることにしばらく気づけなかった。配列をvectorに変更して対処。実行してみると一部答えの符号が違ったり定数分ずれているだけだったので方針は合ってると信じてサンプル通るように微調整。終了2分前にサンプル通ること&最大ケースでTLEしないことだけを確認して送信。
チャレンジフェーズはあまり積極的にやらずに分かりやすいものだけを落とす方針でやった。結果一つも落とせなかったけどまあ仕方ない。チャレンジ1成功くらいだとあまり順位上がらない位置だったし。