二分探索②：解を仮定して判定（全４回）

解を仮定して判定（最大値）

二分探索 を使うと、ある条件を満たす最大値を求めるときに非常に有用です。

問題

Ｎ本の紐 があり長さはそれぞれ異なります。

これらの紐を切って、同じ長さの紐をＫ本 作るときの 最長の長さ を求めなさい。

答えは小数点以下２桁までを切り捨ててください。

ソースコード

区間の 下端ｌｂを条件満たす値 に、上端ｕｂを条件を満たさない値 にそれぞれ初期化し、解の存在範囲（ｌｂ、ｕｂ）が十分小さくなるまで、中央の値が条件を満たすかどうか判定し存在範囲を狭めていきます。

最終的に、ｌｂが求めたい 最大の値 となります。

[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
#------ 入力例 ------
lst = [8.12, 7.53, 4.47, 5.29]  # 各紐のながさ
k = 11           # 作りたい同じ長さの紐の本数
#--------------------
n = len(lst)    # 紐の本数

# 長さｘの紐をｋ本作れるかどうか
def check(x):
    cnt = sum([int(l / x) for l in lst])
    return cnt >= k

lb = 0         # 初期化（下限の範囲）
ub = 999999    # 初期化（上限の範囲）

# 解の存在範囲が十分狭くなるまで繰り返す
for _ in range(99):
    mid = (lb + ub) / 2
    if check(mid):
        lb = mid
    else:
        ub = mid

# 小数点第２までを切り捨て
print(('解: {:.2f}').format(lb * 100 // 100))

[実行結果]

解: 2.00

長さが２ であれば、１１本の同じ長さの紐 が作れることを導き出すことができました。

解を仮定して判定（最小値）

上記の処理と同様にある条件を満たす 最小値 を求めることもできます。

区間の 下端ｌｂを条件満たさない値 に、上端ｕｂを条件を満たす値 にそれぞれ初期化し、解の存在範囲（ｌｂ、ｕｂ）が十分小さくなるまで、中央の値が条件を満たすかどうか判定し存在範囲を狭めていきます。

最終的に、ｕｂ が求めたい 最小の値 となります。