CODE FESTIVAL2015-D 壊れた電車

内容

• CODE FESTIVAL2015　予選A D問題「壊れた電車」をpythonで解いた。
• 二分探索をバグらせがちなので、メモとして。

問題

atcoder.jp

考えたこと

• 最小値を求める問題で、にぶんたんができそうなので、　にぶたんする。

  ポイント

• シミュレーションの時に、左の車両から優先して掃除するようにする。

実装

N,M = map(int,input().split())
POS=[int(input())-1 for _ in range(M)]

low=0
high=2*N

def check(x):
    """
    x-minuteで掃除できるか (True/False)
    """

    #掃除していない最右車両
    dirty_right=0 
    for pos in POS:
        if dirty_right<pos: #自分より左側に未掃除の領域がある
            to_left_move = pos-dirty_right #　必要な左移動の数
            if to_left_move>x: #　境界まで届かない
                return False
            else:
                # right-first (一旦右行ってから左に行く)
                right_first=pos+max(x-to_left_move*2,0)+1
                # left_first (一旦左に行ってから右に行く)
                left_first = pos+max((x-to_left_move)//2,0)+1

                dirty_right = max(right_first,left_first)
        else: #できるかぎり右まで綺麗にする
            dirty_right = max(dirty_right,pos+x+1)

    #N車両全部掃除できた?
    if dirty_right<N:
        return False
    return True

while low<=high:
    mid = (low+high)//2
    if check(mid):
        high=mid-1
    else:
        low=mid+1
print(low)

終わりに

• WAの時に、check()が間違っているのか、二分探索の更新とか終了条件が間違っているのかわからずに、詰まった。
• にぶたんの書き方を、テンプレ化して、にぶたんの部分のバグに悩まないで済むようにしたい。