Binary Search the Answer - Sparsely Planting Trees
与えられた
n 個の植樹可能な場所があるとき、将来的に木々が互いに邪魔し合わないよう、できるだけまばらに木を植えたいとします。それぞれのスポットの座標は整数 で与えられます。あなたの課題は、
t 本の木を植えたときに得られる木同士の最小距離を、可能な限り大きくすることです。入力
入力の最初の行には、植樹可能な場所の数を表す整数
n (1 ≤ n ≤ 100000) と、実際に植える木の本数を表す整数 t (2 ≤ t ≤ n) が与えられます。次の行には、
n 個の異なる整数 (0 ≤ ≤ ) が空白区切りで与えられ、これは木を植えられるスポットの座標を示します。出力
できる限りまばらに木を植えたときに、木同士の最小距離がいくつになるかを表す整数
d を出力してください。例
Input | Output |
5 3
1
2
8
4
9 | 3 |
説明
座標 1, 4, 9 に木を植えると、最小距離は 4 - 1 = 3 になります。
Tutorial
この問題は「解答に対するバイナリサーチ（Binary Search on the Answer）」という手法を使うことで解決できます。これは、求めたい“最小距離”を二分探索の対象にして、ある候補となる最小距離で木を植えられるかどうかを反復的にチェックする方法です。二分探索を利用するためには以下のような条件が必要です:
- 候補となる答えが問題の要件を満たしているかどうかを判定できる。ここでは、「候補の最小距離
dを確保しつつt本の木を植えることが可能かどうか」を調べられればOKです。
- チェック用の関数
def check(x):が、与えられた候補値xに対して要件を満たせるならTrue、そうでなければFalseを返すものになっていること。
- 候補値を小さい方から大きい方へと変化させたとき、ある地点から先のすべての値について判定結果が変わらない（例えば最初は不可能だが、ある大きさ以降は可能になる、もしくはその逆）が条件になります。
False False False True True(impossible for the first several numbers and then possible for larger ones). In this case, we’re looking for the firstTrue(the smallest valid value).True True True True False False(possible for small numbers and impossible for larger ones). In this case, we’re looking for the lastTrue(the largest valid value).
In our case, we would like to plant the trees as sparsely as possible. So, we would like the minimum distance to be as large as possible. If it’s possible to plant trees with a minimum distance of
x, then it’s definitely possible to plan them denser and get a smaller x. Therefore, in our case, the values of the checking function will be True True True True False False and we aim to find the last True in this list (the largest (most sparse) minimal distance between the planted trees).今回のように「木をできるだけまばらに植えたい」場合、求めたい最小距離が大きい方がよいので、もし「距離が
x でも植えられる（True）」のであれば、それより小さい距離でも当然植えられるはずです。したがって、候補値をだんだん大きくしていくと、最初の方は True が続き、ある地点から False へと変わる──というふうに振る舞うはずです。私たちの目的は、その変わる直前の最大の True を探すことで、「木々を最もまばらに植えられる最小距離」を求めることになります。単純な方法としては、1 から順番に候補となる距離
d を増やしながら、d を確保できるか毎回チェックする方法が考えられますが、これでは時間がかかりすぎるかもしれません。そこで二分探索を使うと効率よく解が求められます。まずはチェック関数から見てみましょう:
n, t = ...
x = sorted(x)
def check(d):
""" Check if we can plant t trees at least d units apart """
planted = 0 # t 本のうち、今何本植えたか（初期値は 0）
prev = float('-inf') # 直前に植えた木の座標を記憶しておく
for xi in x:
if xi - prev >= d: # d 以上離れていれば新たに植えられる
planted += 1
prev = xi
return planted >= tこのように、与えられた候補の距離
d で木を植えられる本数が t 本以上になれば True を返す、という仕組みです。l, r = 1, max(x) # 最小距離が取りうる範囲を [l, r) として設定
while r - l > 1: # l と r の間にまだ候補があるうちはループ
mid = (l + r) // 2 # 中間値を計算
if check(mid): # mid の距離が実現できるか確認
l = mid
else:
r = mid
print(l)Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB