概要

一本道の地点 \(1\) からスタートし、通行止めの区間を最大 \(M\) 個まで許可証で突破しながら、右方向にどこまで到達できるかを求める問題です。

考察

重要な気づき：一本道は「一方向」にしか進めない

地点は一列に並んでおり、高橋君は地点 \(1\)（左端）にいます。到達できる地点を増やすには、右方向に進むしかありません。

ここで重要なのは、途中の通行止めを飛ばして先に進むことはできないという点です。例えば、地点 \(2\) と地点 \(3\) の間が通行止めなら、これを突破しない限り地点 \(3\) 以降には絶対に到達できません。

具体例

\(N = 6, M = 2\), \(W = [0, 1, 0, 1, 1]\) の場合を考えます。

地点: 1 --- 2 -×- 3 --- 4 -×- 5 -×- 6
         W1=0  W2=1  W3=0  W4=1  W5=1

• 地点 \(1 \to 2\)：通行止めなし → そのまま通過
• 地点 \(2 \to 3\)：通行止め → 許可証 1 枚目を使用（残り 1 枚）
• 地点 \(3 \to 4\)：通行止めなし → そのまま通過
• 地点 \(4 \to 5\)：通行止め → 許可証 2 枚目を使用（残り 0 枚）
• 地点 \(5 \to 6\)：通行止め → 許可証がもうない → ここで停止

到達できる地点は \(1, 2, 3, 4, 5\) の 5 個です。

なぜ貪欲法で良いのか

通行止めを「スキップ」して遠くの区間に許可証を使う、といった戦略は意味がありません。地点 \(1\) から連続して繋がっていなければ到達できないため、左から順番に通行止めに遭遇したら許可証を使うという貪欲法が最適です。

アルゴリズム

1. 地点 \(1\) から右方向に区間を順番に見ていく。
2. 区間 \(i\)（地点 \(i\) と地点 \(i+1\) の間）が通行止め（\(W_i = 1\)）なら、許可証を 1 枚使う。
3. 許可証の使用枚数が \(M\) を超えたら、そこで探索を打ち切る。
4. 通過できた区間の数 \(+1\)（地点 \(1\) 自身）が到達可能な地点の数。

計算量

• 時間計算量: \(O(N)\) — 区間を左から順に最大 \(N-1\) 個見るだけ
• 空間計算量: \(O(N)\) — 通行止め情報 \(W\) の格納

実装のポイント

• \(N = 1\) の場合：区間が存在しないため、入力の2行目の処理に注意が必要です。地点 \(1\) のみで答えは \(1\) です。

• ループの終了条件：許可証を \(M\) 枚使い切った次の通行止めに遭遇したときに break します。used > M という条件で判定しています。

• reach の初期値：地点 \(1\) に最初からいるので、初期値を \(1\) として、区間を1つ通過するごとに \(1\) 加算します。

  ソースコード

def solve():
    N, M = map(int, input().split())
    if N == 1:
        print(1)
        return
    W = list(map(int, input().split()))
    
    # 高橋君は地点1にいて、右方向に進む（一本道なので左には地点がない）
    # 通行止めの区間をM枚まで突破できる
    # 地点1から連続して右に進み、通行止めに遭遇したら許可証を使う
    # 許可証をM枚使い切ったらそこまで
    
    used = 0
    reach = 1  # 地点1には既にいる
    
    for i in range(N - 1):
        if W[i] == 1:
            used += 1
            if used > M:
                break
        reach += 1
    
    print(reach)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。