概要
競プロ典型90問の解説記事です。
解説の画像を見ても分からない（理解力が足りない）ことが多々あったので、後で解き直した際に確認できるようまとめました。
※順次、全ての問題の解説記事を挙げていく予定です。
問題001-Yokan Party
問題概要
長さLのようかんをK+1個に切り分けた時のピースの中で最も小さいピースの最大値を求める。
ただし、切り分ける場所は、N箇所のいずれか(A1 ~ AN)で指定されている。
制約
1 <= K <= N <= 100000 \\
0 < A1 < A2 < ・・・ < AN < L <= 10^9
解き方
全ての切り分け方を求めてから計算する方法は、
N個の切れ目からK個選ぶパターン、すなわちnCk通りを調べることになり、NG。
そこで今回は、
- X(cm)以上の長さでようかんを切り分けられるかを判定する
- 1~Lまでで上記1の判定を通るものの最大値を求める
といった流れで実装していく。
１に関して、ようかんの端から順に切れ目を見ていき、X（cm）以上になったら
ようかんのピースを+1（個）するといった形で実装できる。
この時の計算量は、O(N)。
2に関して、1~Lに対して、二分探索を用いることによって、
判定を満たす最大値を求められる。（二分探索に関してはこちら）
この時の計算量は、O（logL）。
判定の計算量がNで、判定する際の計算量がlogLのため、
合計でO(NlogL)。これは約10の6乗になるので、十分に間に合う。
引用元：競プロ典型90問 Github
実装
answer.py
# 入力の受け取り
N, L = map(int, input().split())
K = int(input())
# 先頭に0、末尾にLを追加することで切れ目の差を求めやすくする
A = [0]+list(map(int, input().split()))
A.append(L)
# 判定するメソッド。cntで切れ目の差の合計がx以上になった時の個数を計測。lで切れ目の差を加算していく。（x以上になったらlはリセット）
def check(x):
cnt = 0
l = 0
for i in range(N+1):
l += A[i+1] - A[i]
if l >= x:
cnt += 1
l = 0
return cnt >= K+1
# 二分探索のテンプレ
ng = L
ok = -1
while ng - ok > 1:
mid = (ok + ng) // 2
if check(mid):
ok = mid
else:
ng = mid
# 二分探索により、okにcheckがtrueになる、最大値が入っているので、okを出力
print(ok)
最後に
問題の解説を読んでも他の人のコードを見てもさっぱり分からないという方の
力に少しでもなれれば幸いです。
（自分は最初、さっぱり分かりませんでした。）
ここまでお読みいただきありがとうございました。