Educational Codeforces Round 61
A、B、Cはpretestが通ったが、Cがhackされてしまった。C問題は本当に計算量が大丈夫なのか少し自信がなかったが、WAでhackされていたので不思議に思って確認してみると、iとjを書き間違えている部分があった。なぜprerestに通ってしまったのだろう。
C問題は単純に累積和を取ってから取り除く塗装屋の全ての組み合わせを試していたら間に合わないので、枝刈りをした。おそらく、担当する全ての区間に三人以上の塗装屋が担当している人を取り除けば間に合うということが分かるのだが、厳密に示してはいない。とりあえず、それでACは取れた。想定解法ではない気がするので、Editorialが出たら確認したい。
（追記）Editorialをみた。賢くやると普通に全ての組み合わせが試せるということがわかった。僕の枝刈りと使っている情報は同じなのだが、明らかに想定解法の方が綺麗だし、時間複雑度が明らかなので良いですね。
F問題も単純にDPだろうと思ったのだが、なぜか通らなかった。他の人の解法をみてみると凄く効率の良い書き方をしていて、十数行程度でかけるらしい。しかし本質的な部分は変わらないように見えるので、僕のコードがなぜ通らなかったのかは未だに良くわかっていない。
F問題の想定解法は普通に頭良いと思うんだけれど、多くの人が全く同じ解法で解いているので典型的な解き方なのかもしれない。
F問題はともかくとして、C問題は勿体無かった。しかしレートが1500に戻った。とりあえず今回のCとFみたいに解法が分かる問題はしっかりと取れるようにしたい。
あと最近気づいたことだけれど、僕は実装が遅いというだけではなくて特にレート上位の人に比べると単純にコードが無駄に長いということが分かってきた。これはバグが多い原因の一つでもあると思う。時間複雑度が間に合う解法を思いついたらすぐに書き始めてしまうのだけれど、効率の良い短いコードで実現できるかを考えてから書き始めるようにしたい。
