Overview

Starting from point \(1\) on a straight road, determine how far to the right you can reach while using permits to break through at most \(M\) blocked sections.

Analysis

Key Insight: You can only travel in one direction on a straight road

The points are arranged in a line, and Takahashi is at point \(1\) (the left end). To reach more points, he can only move to the right.

The important thing here is that you cannot skip over a blocked section to proceed further ahead. For example, if the section between point \(2\) and point \(3\) is blocked, you absolutely cannot reach point \(3\) or beyond without breaking through it.

Concrete Example

Consider the case \(N = 6, M = 2\), \(W = [0, 1, 0, 1, 1]\).

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

• Point \(1 \to 2\): Not blocked → Pass through freely
• Point \(2 \to 3\): Blocked → Use 1st permit (1 remaining)
• Point \(3 \to 4\): Not blocked → Pass through freely
• Point \(4 \to 5\): Blocked → Use 2nd permit (0 remaining)
• Point \(5 \to 6\): Blocked → No permits left → Stop here

The reachable points are \(1, 2, 3, 4, 5\), for a total of 5.

Why a Greedy Approach Works

Strategies like “skipping” a blocked section to save a permit for a farther section are meaningless. Since you cannot reach a point unless it is continuously connected from point \(1\), the greedy approach of using a permit each time you encounter a blocked section from left to right is optimal.

Algorithm

1. Examine the sections in order from point \(1\) to the right.
2. If section \(i\) (between point \(i\) and point \(i+1\)) is blocked (\(W_i = 1\)), use one permit.
3. If the number of permits used exceeds \(M\), stop the search there.
4. The number of sections passed through \(+ 1\) (point \(1\) itself) is the number of reachable points.

Complexity

• Time complexity: \(O(N)\) — We examine at most \(N-1\) sections from left to right
• Space complexity: \(O(N)\) — Storing the blocked section information \(W\)

Implementation Notes

• Case \(N = 1\): No sections exist, so care must be taken when processing the second line of input. The answer is \(1\) since only point \(1\) exists.

• Loop termination condition: We break when we encounter the next blocked section after using all \(M\) permits. This is checked with the condition used > M.

• Initial value of reach: Since we start at point \(1\), the initial value is \(1\), and we add \(1\) for each section we pass through.

  Source Code

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()

---

This editorial was generated by claude4.6opus-thinking.