二分探索③:最小値の最大化(全4回)

最小値の最大化

前回に引き続き、二分探索 を使って 最小値の最大化 を求める問題を解いてみます。

問題

おじいさんがN個の小屋を作りました。小屋は直線状に並んでいます。

おじいさんは馬をM頭飼っていますが、それぞれの馬ができるだけ離れるように

小屋にいれたいと考えています。

最も近い2頭の馬の間隔を 最大化 するためには馬をどのように

小屋に入れたらよいでしょうか。

ソースコード

この問題は、ある条件を満たす最大値を求める問題です。

下記のような手順で問題を解いていきます。

  1. 小屋の位置を昇順にソートする。
  2. 最初の馬を1番目の小屋に入れる。
  3. 次の馬を2番目の小屋にいれて、ある間隔を確保できるかどうかチェックする。
  4. もし間隔があけられなければ、次の小屋に移動し再び間隔のチェックを行う。
  5. ある間隔を確保できたら、(間隔を確保できた)小屋の位置を基準にして次の馬を入れる小屋の位置を同じようにチェックする。
  6. 途中で小屋がなくなったら、条件を満たすことができなかったと判定する。
  7. 最後の馬まで小屋にいれることができたら条件を満たせたと判定する。
  8. 2~7の判定を二部探索を使って、解の存在範囲(馬同士の間隔)を狭めながらチェックする。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#------ 入力例 ------
m = 3 # 馬の頭数
lst = [1, 2, 8, 4, 9] # 小屋の位置
#--------------------
n = len(lst) # 小屋の数

# 条件を満たす距離かどうかを判定
def check(d):
last = 0 # 小屋の位置①
for _ in range(m - 1):# 最初の馬は1番目の小屋に入れるので(馬の頭数 - 1頭)分ループする
crt = last + 1 # 小屋の位置②
# 小屋の位置が存在し かつ
# 小屋の位置①と小屋の位置②がある距離[d]未満だったら
while crt < n and lst[crt] - lst[last] < d:
crt += 1 # 小屋の位置2を後ろにずらす(距離[d]を確保するため)
if crt == n: # 最後の小屋の位置をこえたら
return False # 条件を満たさない
last = crt # 条件を満たしたので、小屋の位置①を小屋の位置②に移動
return True # すべての馬を小屋にいれられたので条件を満たす

lst = sorted(lst) # 小屋の位置を昇順にソート

# 解の存在範囲を初期化
lb = 0
ub = 9999
# 条件を満たすかどうか解の存在範囲を狭めながらチェックする
while ub - lb > 1:
mid = (lb + ub) // 2
if check(mid):
lb = mid
else:
ub = mid
print('解:', lb)

[実行結果]

解: 3

馬の間隔を3ずつあければうまく馬をいれられることが分かりました。

つまり 位置1,4,9 の小屋に馬を格納すれば、最も近い2頭の馬の 間隔を最大化 することができることになります。