AtCoder Beginner Contest 023D 射撃王
ABC023D 射撃王を解きました。
初見では全然歯が立たず、解説を読んでなんとか解くことができました。
以下本問題を解いて気がついたところです。
最大となるものを最小にする
この問題一見すると、なんとか工夫して貪欲法を使って最小化を行うことができるように見えてしまいます。
私は一秒後の高さが高い順に消していけばうまくいくのではないかという直感を元に解こうとしましたが、あえなく撃沈。。
そう、この問題そのままでは最適化をうまく行うことができないのです。。
どういう風に問題を読み替えれば、この最適化問題を解きやすい形に変換できるか？を考える必要があります。
この問題は、すべての風船をX以下の高度で撃ち落とすとした場合の最小のXを求める、という問題に置き換えることできます。
この発想の転換が問題攻略の第一の鍵です。
二分探索！二分探索！二分探索！
問題を置き換えることができても、そのXなるものをどうやって求めれば良いのでしょうか？
貪欲に全ケースを試していては時間が足りなくなるケースがでてきてしまいます。
そこで二分探索の出番です！
Xは条件に対して単調なので（ある数以上のXはすべて条件を満たし、ある数より小さいXはすべて条件をみたさない）、二分探索を適用することができます。
二分探索の適用を思いつけるかが問題攻略の第二の鍵です。
[Xとしてあり得る数の最小値 - 1, Xとしてあり得る数の最大値 + 1]の範囲で二分探索をつかって探索を行い、条件を満たすXの最小値が答えになります。
ちなみに、探索範囲を[Xとしてあり得る数の最小値, Xとしてあり得る数の最大値 ]とするとコーナーケースでひっかかってしまうので注意してください。
終わりに
次は独力で解けるようにします。
