Overview

This problem is a shortest path problem where you walk along a corridor of \(N\) tiles lined up in a row, advancing 1 or 2 steps at a time toward the goal (tile \(N\)), while minimizing the number of footprints (tiles where dust has decreased).

Analysis

First, let’s organize when a “footprint is left.” When stepping on tile \(i\), a footprint is left only if there is originally dust (\(H_i > 0\)) and stepping on it reduces the dust (\(D_i > 0\)). If \(H_i = 0\), there is no dust to begin with so nothing changes, and if \(D_i = 0\), stepping on it does not reduce the dust.

Therefore, for each tile \(i\), we can define the cost \(C_i\) incurred when stepping on it as follows: - When \(H_i > 0\) and \(D_i > 0\): \(C_i = 1\) - Otherwise: \(C_i = 0\)

Takahashi starts from tile 1 and moves from the current position \(j\) to \(j+1\) or \(j+2\). This rule has the same structure as the classic “climbing stairs problem” and can be solved using dynamic programming (DP).

Algorithm

Dynamic Programming (DP)

We define the following DP table: - dp[i]: the minimum number of footprints left when reaching tile \(i\)

1. Initial State

• Tile 1 must always be stepped on: dp[1] = C_1
• Tile 2 can only be reached by moving from tile 1: dp[2] = dp[1] + C_2

2. Transition

There are two ways to reach tile \(i\) (\(i \ge 3\)): “come from tile \(i-1\) with 1 step” or “come from tile \(i-2\) with 2 steps.” Since we want to minimize the number of footprints, we choose the smaller value. $\(dp[i] = \min(dp[i-1], dp[i-2]) + C_i\)$

3. Answer

The final answer is dp[N].

Complexity

• Time Complexity: \(O(N)\) For \(N\) tiles, we scan each tile once and update the DP value, so the computation finishes in linear time. Since \(N \leq 2 \times 10^5\), this is sufficiently fast.
• Space Complexity: \(O(N)\) Storing the cost \(C_i\) for each tile requires \(O(N)\). The DP table itself can be reduced to \(O(1)\) by only keeping the two most recent values.

Implementation Notes

• Fast I/O: In Python, using sys.stdin.read().split() allows reading large amounts of input data at once efficiently.

• Memory Saving: By reusing just two variables, dp_prev1 and dp_prev2, the DP can be updated without preparing an array of length \(N\).

• Index Adjustment: The problem statement is 1-indexed (1st, 2nd, …), but in programs it is common to use 0-indexed (0th, 1st, …), so care must be taken with the offset.

  Source Code

import sys

def solve():
    # 入力を一度にすべて読み込む（高速化のため）
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    # 入力が空の場合の処理
    if not input_data:
        return
    
    # N: タイルの枚数
    N = int(input_data[0])
    
    # 各タイルを踏んだときに足跡が残るかどうかを判定
    # H_i > 0 かつ D_i > 0 のとき、タイル i に足跡が残る
    # costs[i] はタイル i+1 に足跡が残るなら 1、そうでなければ 0
    # Hの値は input_data[1] から input_data[N] に格納されている
    # Dの値は input_data[N+1] から input_data[2*N] に格納されている
    costs = [0] * N
    for i in range(N):
        h = int(input_data[1 + i])
        d = int(input_data[1 + N + i])
        if h > 0 and d > 0:
            costs[i] = 1
    
    # 動的計画法 (DP) を用いて足跡の最小数を求める
    # dp[i] はタイル i+1 に到達するまでに残る足跡の最小数
    # 制約より N >= 2 なので、最初の2つのタイルのベースケースを計算
    
    # タイル1 (インデックス0) は必ず踏む
    dp_prev2 = costs[0]
    
    # タイル2 (インデックス1) はタイル1から移動してくる必要がある
    dp_prev1 = costs[0] + costs[1]
    
    # N=2 の場合は、タイル2に到達した時点の値を表示して終了
    if N == 2:
        print(dp_prev1)
        return
        
    # タイル3 (インデックス2) から タイルN (インデックスN-1) まで計算
    # dp[i] = min(dp[i-1], dp[i-2]) + costs[i]
    # メモリ節約のため、直近2つのDP値のみを保持する
    for i in range(2, N):
        # 現在のタイル i への最小足跡数 = min(1つ前のタイルから, 2つ前のタイルから) + 現在のタイルのコスト
        if dp_prev1 < dp_prev2:
            current_dp = dp_prev1 + costs[i]
        else:
            current_dp = dp_prev2 + costs[i]
        
        # 次のループに向けて値を更新
        dp_prev2 = dp_prev1
        dp_prev1 = current_dp
        
    # タイルN (インデックスN-1) に到達したときの最小足跡数を出力
    print(dp_prev1)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.