このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。
問題
ポイント
K+1 個のピースのうち最も短いものの長さをXcmと置いて考えます。
この問題では最大のX（=スコア）を求めたいのですが、ここでXの候補は1cmからLcmまでの
合計L個あります。
それぞれのXの候補に関して条件を満たすかを確かめるためには、シンプルに羊羹の左端からXcm以上になるようにピースを取っていき、全体でK+1以上のピースを確保できるかを考えればよいです。
ただし、全てのXの候補に対して上記の確認を行うと、残念ながらTLEとなってしまいます。
そこで、Xの候補を確認する際に二分探索を使用します。
二分探索をご存知ない方には以下のページの説明が分かりやすくおすすめです。
※特に最初に置くok,ngと探索範囲の関係性について良く読んで理解しておくと今後役に立ちます。
AtCoder灰・茶・緑色の方必見！二分探索を絶対にバグらせないで書く方法
以上を踏まえ、実装したコードがこちらです。
コード
def main():
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
N, L = map(int,input().split())
K = int(input())
A = [0] + list(map(int,input().split())) + [L]
# ようかんをXcm以上のK+1個のピースに分けられるか確認
def check(l):
left_idx, right_idx = 0, 0
cnt = 0
while right_idx < len(A):
if A[right_idx] - A[left_idx] < l:
right_idx += 1
else:
cnt += 1
left_idx = right_idx
right_idx += 1
return True if cnt >= K+1 else False
# Xの候補を二分探索
ok, ng = 1,L+1
while ng - ok > 1:
mid = (ok + ng) // 2
if check(mid):
ok = mid
else:
ng = mid
print(ok)
if __name__ == '__main__':
main()
