競プロ典型90問：001 - Yokan Party（★4）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_a

挑戦結果

• 解けなかった
• 時間：30分ぐらい

考えたこと

• 苦手なDPと思ってずっと考えていたけど、あきらめた。
• 解説を見たら「答えで二分探索」の問題だった

解説を読んだあとのふりかえり

• 長さM以上のピースに分割できるかの関数を作った。けっこうハマって時間がかかった。
• 作成した関数をforで回して結果を確認。この戻り値がTrue→Falseになる瞬間を二分探索でもとめればOKであることを確認。
• 二分探索を作成。これはスムーズにできた。

ソース

# Keyword：答えで二分探索

# インプット
N, L = [int(x) for x in input().split()]
K = int(input())
A = [int(x) for x in input().split()]
# 計算用に先頭と末尾に加えておく
A = [0] + A + [L]

# 長さM以上のピースに分割できるか？
def check(M):
    l = cnt = 0
    for i in range(N+1):
        l += (A[i+1] - A[i])
        if l>=M:
            l=0
            cnt +=1
    # return cnt > K or (cnt == K and l>=M)
    return cnt > K 

#### デバッグ・確認用
# 二分探索をせずに各スコアのの実現可否の列挙
# Trueである最も大きい値がこの問題の答え。
# for i in range(1,L):
#     print(f"{i}, {check(i)}")

# 二分探索。lはTrue、rはFalseを想定。
def binarysearch(l,r):
    # 終了条件
    if l+1 == r:
        return l
    # lとrの中間のTrue/Falseで範囲を狭くする
    m = (l + r) //2
    if check(m):
        return binarysearch(m, r)
    else:
        return binarysearch(l, m)

# 二分探索で求める
print(binarysearch(1, L))