最小値の最大化
前回に引き続き、二分探索 を使って 最小値の最大化 を求める問題を解いてみます。
問題
おじいさんがN個の小屋を作りました。小屋は直線状に並んでいます。 おじいさんは馬をM頭飼っていますが、それぞれの馬ができるだけ離れるように 小屋にいれたいと考えています。 最も近い2頭の馬の間隔を 最大化 するためには馬をどのように 小屋に入れたらよいでしょうか。
ソースコード
この問題は、ある条件を満たす最大値を求める問題です。
下記のような手順で問題を解いていきます。
- 小屋の位置を昇順にソートする。
- 最初の馬を1番目の小屋に入れる。
- 次の馬を2番目の小屋にいれて、ある間隔を確保できるかどうかチェックする。
- もし間隔があけられなければ、次の小屋に移動し再び間隔のチェックを行う。
- ある間隔を確保できたら、(間隔を確保できた)小屋の位置を基準にして次の馬を入れる小屋の位置を同じようにチェックする。
- 途中で小屋がなくなったら、条件を満たすことができなかったと判定する。
- 最後の馬まで小屋にいれることができたら条件を満たせたと判定する。
- 2~7の判定を二部探索を使って、解の存在範囲(馬同士の間隔)を狭めながらチェックする。
[Google Colaboratory]
1 | #------ 入力例 ------ |
[実行結果]
解: 3
馬の間隔を3ずつあければうまく馬をいれられることが分かりました。
つまり 位置1,4,9 の小屋に馬を格納すれば、最も近い2頭の馬の 間隔を最大化 することができることになります。