Overview

Each tile in the corridor has dust on it, and when Takahashi steps on a tile, the dust decreases. Takahashi starts from tile 1 and aims to reach tile N, and in one move he can advance by 1 or 2 squares. We need to find a path that minimizes the number of tiles where dust has decreased (i.e., where footprints are left) due to Takahashi passing through.

Analysis

The essence of this problem is that the number of footprints changes depending on “which tiles are stepped on.” A footprint is left on tile \(i\) only in the following case:

• Initial dust \(H_i > 0\) and decrease amount \(D_i > 0\)

This is a property of the tile itself, and regardless of whether Takahashi steps on that tile, tiles that do not satisfy this condition will never leave a footprint. Therefore, we can determine in advance whether each tile “has the potential to leave a footprint.”

Next, by choosing his path, Takahashi can to some extent choose which tiles to step on. For example, if tile \(i\) would leave a footprint, it is possible to avoid the footprint by choosing a path that does not pass through that tile (however, there is the constraint that he must ultimately reach tile \(N\)).

In this way, we can think of this as a “shortest path problem where we choose whether or not to pass through vertices that incur a cost.” The “cost” here refers to the number of tiles that leave footprints.

A naive approach would be to explore all paths, but since the number of tiles \(N\) can be up to \(2 \times 10^5\), recursion or brute-force search would not finish in time. Therefore, we solve this efficiently using dynamic programming (DP).

Algorithm

We use dynamic programming (DP).

Steps

1. Preprocessing: For each tile \(i\), determine whether a footprint is left: $\( \text{footprint}[i] = \begin{cases} 1 & \text{if } H_i > 0 \text{ and } D_i > 0 \\ 0 & \text{otherwise} \end{cases} \)$

2. DP Table Definition: $\( dp[i] := \text{the minimum number of footprints upon reaching tile } i \)\( Since tile \)i\( itself is stepped on, \)\text{footprint}[i]$ is added.

3. Initialization:

   • \(dp[0] = \text{footprint}[0]\) (starting from tile 1)

4. Transition: For each \(i = 2, 3, ..., N-1\): $\( dp[i] = \min(dp[i-1], dp[i-2]) + \text{footprint}[i] \)$ This means choosing whichever has fewer footprints: “coming from one step before” or “coming from two steps before.”

5. Answer: \(dp[N-1]\) is the desired answer.

Example

Sample input:

5
1 0 2 3 0
1 1 2 1 1

• footprint array: [1, 0, 1, 1, 0]
• DP transitions:
  • dp[0] = 1
  • dp[1] = dp[0] + 0 = 1
  • dp[2] = min(dp[1], dp[0]) + 1 = 2
  • dp[3] = min(dp[2], dp[1]) + 1 = 2
  • dp[4] = min(dp[3], dp[2]) + 0 = 2

→ Answer: 2

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• The footprint calculation is done in preprocessing and used during DP table updates for efficiency.

• Be careful that the DP table does not cause index errors during initialization (e.g., when N=2).

• sys.stdin.read is used for fast input reading.

  Source Code

import sys
import heapq

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    H = list(map(int, data[1:N+1]))
    D = list(map(int, data[N+1:2*N+1]))
    
    # 足跡が残る条件：D[i] > 0 かつ H[i] > 0
    # つまり、D[i] > 0 かつ H[i] > 0 のとき、タイル i は必ず足跡が残る
    # ただし、高橋君は経路を選ぶことで、どのタイルを踏むかを選べる
    # タイル i に足跡が残るかどうかは、(H[i] > 0 and D[i] > 0) で判定可能
    
    # 各タイルについて、足跡が残るかどうかを前もって計算
    footprint = [1 if H[i] > 0 and D[i] > 0 else 0 for i in range(N)]
    
    # dp[i] := タイル i に到達したときの、足跡の最小数
    # ただし、タイル i 自体を踏むので、footprint[i] を加算する
    # 遷移は、i-1 または i-2 から来ることができる
    # dp[0] はタイル1（index 0）からスタートなので、footprint[0]
    
    dp = [float('inf')] * N
    dp[0] = footprint[0]
    
    if N > 1:
        dp[1] = dp[0] + footprint[1]
    
    for i in range(2, N):
        dp[i] = min(dp[i-1], dp[i-2]) + footprint[i]
    
    print(dp[N-1])

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.