概要

地点が一直線に並ぶ道路で、通行止め区間を許可証で最大 \(M\) 個まで開通できるとき、地点 \(1\) から到達できる地点数の最大値を求めます。

考察

この問題の重要な点は「道路が一直線（分岐なし）」であることです。

• 地点 \(1\) から右へ進むには、区間 \((1,2)\)、\((2,3)\)、… を順番に通るしかありません。
• つまり、地点 \(k\) に到達できる条件は
  「区間 \(1\) から \(k-1\) の間にある通行止め（\(W_i=1\)）の数が \(M\) 以下」であることです。
  なぜなら、その通行止めをすべて開通しない限り、その先へは進めないからです。

ここから分かること： - 許可証をどこに使うか迷う必要はありません。到達可能範囲を広げるには、左から順に進み、遭遇した通行止めを必要に応じて開通するしかありません。 - もし「どの区間を開通するか」を組合せで全探索すると、最大で \(2^{N-1}\) 通りになり \(N \le 2\times 10^5\) では到底間に合いません（TLE）。

したがって、左から順に通行止め数を数え、\(M\) を超えた時点で止めればよいです。

例： - \(W = [0,1,0,1,1]\), \(M=2\) のとき
左から通行止め数を数えると \(0,1,1,2,3\) となり、3つ目の通行止めに到達した瞬間（通行止め数が 3）で進めなくなります。
よってそこまでの地点数が答えです。

アルゴリズム

1. cnt = 0（これまでに出会った通行止めの数）、reachable = 1（到達できる最大地点番号）で初期化。
2. \(i=1\) から \(N-1\) まで順に区間を見ていく（配列では W[i-1]）。
   • もし \(W_i = 1\) なら cnt += 1。
   • もし cnt > M になったら、それ以上右へは進めないのでループ終了。
   • そうでなければ地点 \(i+1\) に到達できるので、reachable = i+1 を更新。
3. reachable を出力する。

（提示コードでは 0-index のため、区間 W[i] を見た後に到達できる地点は i+2 になります。）

計算量

• 時間計算量: \(O(N)\)（左から1回なめるだけ）
• 空間計算量: \(O(1)\)（入力以外に大きな追加領域を使わない）

実装のポイント

• N=1 のときは区間が存在しないので答えは必ず 1。

• cnt > M になった瞬間に break することで、無駄な処理を減らせます。

• 入力サイズが大きいので、sys.stdin.buffer.read() のような高速入力が安全です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    if N == 1:
        print(1)
        return
    W = data[2:2 + (N - 1)]

    cnt = 0
    reachable = 1
    for i, w in enumerate(W):
        if w == 1:
            cnt += 1
        if cnt > M:
            break
        reachable = i + 2  # can reach point i+2

    print(reachable)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。