AtCoder Beginner Contest 203（Sponsored by Panasonic）で参加者の9.2%しか正解できなかった問題 [ D - Pond ] をPythonで解く
解きました。
答えを見て……
……まぁまぁ、ワタクシも多分にもれず解けなかった90.8%側なわけですが、解答を見せてもらいながら復習してみました。
9.2%という数字は、A問題提出者8393人。
D問題正解者775人。
775 / 8393 = 9.2%
という計算です。
こちらが、その問題。 atcoder.jp
どうやら上級者は、この問題は二分探索だとわかってしまうらしい
はまやんさんの解説を読む。すると
二分探索しよう。
始めてみる・慣れていない場合はピンとこないと思うが、最大値の最小値というのが二分探索では定番であり、 中央値の最小値で使われる場合も何回か見たことがあるのでスムーズに思いついた。
経験以外で思いつくトリガーあるのかな？ちょっと分からない。
なるほどなー。
そういう点から二分探索だろうなと、わかってしまうわけですね。
AtCoder Liveの解説わかりやすい
いつもの黒服長髪の兄さんが説明してくれる、この動画のD問題解説がわかりやすい。
この解説を聞いて、一通りコード書いてみた。
二次元累積和を出すために、上と左に0を一列追加する話が、なんでなのか解説を聞いてるだけだとわからなかったがコードにしてみてわかった。
二次元累積和は求める点の一個左と一個上の値を参照しなければいけないから、必要なのね。
書いたコード
はまやんさんのコード、AtCoder Live、めぐる式二分探索のPython実装を参考に記述。
AtCoderで実行した結果は、
PyPy3(7.3.0) AC
PyPy3.8.2 TLE
PyPy3だと正解にできます。
コンテスト中に書いた自分の実装
「小さい値から順番に、その値の周辺をチェックしてけば、解けるんじゃね？」
と書いてみたんですが、TLE x 17で玉砕。
2214msで、もうちょっとでイケるかと思ったんだけどムリでした。
