【3日目】昨日の復習とか
昨日のE問題
を再考するため、以下の記事を読んで参考にしてみた。
いくつか学んだことを↓
累積和はs[0]=0とする
これは早速このE問題で使えた。半開区間をベースに考える、という発想らしい(s[0] = [0, 0)の累積和 = 0)。dpについても同じ。
めぐる式二分探索
上のように半開区間で考えることに加え、探索区間をok, badと命名する、abs(bad - ok) >1で判定する、など。今回とは直接関係ないが有用そう。
半開区間というのはキーワードになってきそうですね。今後も意識したいところ。
あと個人的な感想としては、境界条件を考えるにあたっては、とりあえず慣れないうちは自力で具体的に立式してみることも有用そうかなと。今回もそれでやりました。
あとはF問題。
F - Silver Woods
rについてのBinary Searchかな…？というところで行き詰まり。どうしても円というのに捉われてしまって、(各点を中心に半径rの円の重なりを考えるのかな…)というところから抜け出せず。どうしてもグラフに帰着させる系の問題は苦手。今度グラフ問題だけで特訓やろうかな。
実装はあらかじめ用意しておいたBinary SearchとUnion-Find Treeで。Binary Searchは早速上のめぐる式を使ってみた。こりゃ便利。汎用性が高い。Union-Find Treeは前用意した時にデバッグしたつもりだったのだが、どうもしていなかったらしく、バグだらけだった…
少し時間が余ったので、上の記事で出てきた尺取り法は未習だったので少し学習。例題として以下の問題をやってみた。
C - 列 (ABC032)
(この頃のABCって今とだいぶ違うんだなーと思ったり)
とりあえずACしたので明日一般化してまとめておく。ここはそんなに苦戦するところはなさそうかな。
