鴨井遼 競技プログラミング

競技プログラミングについての日記(更新は終了しています)

Codeforces Round #540 (Div. 3)

codeforces.com

 

Div. 3なので問題は簡単なのかと思ったら、想像していたよりは簡単ではなかった。結局時間内に解けた問題はA、B、Cだけで、この3問はほぼアルゴリズムとかではなくてプログラミングの問題という感じだったので、あんまり競プロをやったという感覚がない。しかし実装力・速度をあげるのは重要なので、今後も積極的に出られるコンテストには出たいと思う。

Cが終わった時点で1時間20分だった(本来の敗因はCに1時間もかけたことですね・・・)のでDも解けると思ったのだが、実装が間に合わなかった。終了してから見直したら5分くらいで通ってしまったので悲しい気持ちになったが、結局Hardの方はTLEだった。確かに見直してみると時間的に厳しい部分があった。

easyの方針としてはあっていたのだが、解説をみるとhardの方は二分探索するらしい。言われてみれば明らかに二分探索の問題なので、問題をアルゴリズムに結び付ける感覚を養っていきたい。あとは、自分の実装には明らかに無駄があった。計算量を小さくするために終了条件をうまく判定するようにしていたが、コードとしては無駄に複雑になってしまったし、その程度の高速化ではhardは通らないしeasyでは意味がなかった。時間計算量を(ミスなく)見積もって必要最低限のコードをかけるようにしたい。

解法を知ってからDを実装したら、本当にシンプルなコードになった。ちゃんと最初から綺麗な解法を思いつくようになりたい。