概要

この問題は、\(N\) 枚のタイルを一列に並んだ廊下で、1歩または2歩ずつ進みながらゴール（タイル \(N\)）を目指すとき、足跡（ほこりが減少したタイル）の数を最小化する最短経路問題です。

考察

まず、どのような場合に「足跡が残る」のかを整理します。 タイル \(i\) を踏んだとき、もともとほこりがあり（\(H_i > 0\)）、かつ踏むことでほこりが減る（\(D_i > 0\)）場合にのみ足跡が残ります。もし \(H_i = 0\) ならば最初からほこりがないため変化しませんし、\(D_i = 0\) ならば踏んでもほこりは減りません。

したがって、各タイル \(i\) について、踏んだときに発生するコスト \(C_i\) を以下のように定義できます。 - \(H_i > 0\) かつ \(D_i > 0\) のとき： \(C_i = 1\) - それ以外： \(C_i = 0\)

高橋君はタイル 1 からスタートし、現在の位置 \(j\) から \(j+1\) または \(j+2\) へ移動します。このルールは典型的な 「階段を登る問題」 と同じ構造をしており、動的計画法（DP）を用いて解くことができます。

アルゴリズム

動的計画法 (DP)

以下のような DP テーブルを定義します。 - dp[i] ：タイル \(i\) に到達するまでに残る足跡の最小数

1. 初期状態

• タイル 1 は必ず踏むため： dp[1] = C_1
• タイル 2 はタイル 1 から移動してくるしかないため： dp[2] = dp[1] + C_2

2. 遷移式

タイル \(i\) (\(i \ge 3\)) に到達する方法は、「タイル \(i-1\) から 1 歩で来る」か「タイル \(i-2\) から 2 歩で来る」かの 2 通りです。足跡を最小にしたいので、より小さい方を選択します。 $\(dp[i] = \min(dp[i-1], dp[i-2]) + C_i\)$

3. 答え

最終的に dp[N] が求める答えとなります。

計算量

• 時間計算量: \(O(N)\) タイルの枚数 \(N\) に対して、各タイルを 1 回ずつ走査して DP の値を更新するため、線形時間で計算が終わります。\(N \leq 2 \times 10^5\) であるため、十分に高速です。
• 空間計算量: \(O(N)\) 各タイルのコスト \(C_i\) を保持するリストに \(O(N)\) かかります。DP テーブル自体は直近 2 つの値のみを保持するように実装すれば \(O(1)\) まで節約可能です。

実装のポイント

• 高速な入出力: Python の場合、sys.stdin.read().split() を使うことで、大量の入力データを一度に高速に読み込むことができます。

• メモリ節約: dp_prev1 と dp_prev2 という 2 つの変数だけを使い回すことで、長さ \(N\) の配列を用意せずに DP を更新しています。

• インデックスの調整: 問題文は 1-indexed（1番目、2番目…）ですが、プログラム上は 0-indexed（0番目、1番目…）で扱うことが多いため、ズレに注意が必要です。

  ソースコード

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

---

この解説は gemini-3-flash-thinking によって生成されました。