【21日目】二分探索

昨日から二分探索に取り掛かっていたのだが記録していなかったので、併せて書いておく。23だけはまだ途中。

18　ALDS_4_B - 二分探索

upper_boundを使えば一発。時間制限が厳しければ他の方法を取るけれどここはそれで十分。

19　JOI 2009 本選 2 - ピザ

本店を店のリストの両端に入れれば愚直にできる。upper_boundとかlower_boundっていつも境界条件で少し考えてしまう。二分探索するリストにmax, minの値をあらかじめ入れておけば気にせずに済むのかな？

20　AtCoder Beginner Contest 077 C - Snuke Festival

3段というのがミソ。真ん中の段を基準に両側それぞれ二分探索する。

21　AtCoder Beginner Contest 023 D - 射撃王

出ました最大値を最小化する系の問題。この手の問題を二分探索で解けると知った時には感動したし、今でも一番好きなタイプの問題。18~20はupper/lower boundだけで書けたので、ここで初めてまともなbinary search書いた。以前知っためぐる式使ってみたけどやはり使いやすい。境界条件とかで実装少し手間取った。

22　AtCoder Regular Contest 054 B - ムーアの法則

連続的な二分探索。数学的な考察で解く問題。double型だと精度とか考えるの苦手で嫌なんだけどこの問題は特にそういう心配はいらなさそうだった。最後求めるものを間違えて無駄に手間取ってしまった。

23　JOI 2008 本選 3 - ダーツ

まだ途中。2本ずつに分けることで計算量で解こうとしたのだがTLE。N=1000なのに駄目なのか、それとも計算量の見積もりが間違っているのか。