概要

各タイルを踏んだときに「足跡（ほこりが減る）」が残るかどうかを 0/1 のコストに変換し、タイル \(1\) から \(N\) まで 1 または 2 マス進む最小コスト経路問題として動的計画法で解きます。

考察

足跡が残る条件の整理

タイル \(i\) を踏むとほこりは \(D_i\) だけ減少しますが、減少量は最大でも現在の厚さまでです。
この問題では移動が常に右方向（\(+1\) か \(+2\)）なので、同じタイルに戻って踏み直すことはできず、各タイルは高々 1 回しか踏みません。
よってタイル \(i\) の「踏んだ後にほこりが減ったか」は、初期値だけで決まります。

• 初期ほこりが \(H_i = 0\) なら、踏んでも減らない（足跡なし）
• 減少量が \(D_i = 0\) なら、踏んでも減らない（足跡なし）
• \(H_i > 0\) かつ \(D_i > 0\) なら、必ず 1 以上減る（足跡あり）

したがって、各タイルに対し [ A_i = \begin{cases} 1 & (H_i>0 \ \text{かつ}\ D_i>0)\ 0 & \text{それ以外} \end{cases} ] という 0/1 コストを置けば、「足跡の数」は「通ったタイルの \(A_i\) の合計」に一致します。

素朴な方法が難しい理由

移動方法（1 歩 or 2 歩）の組合せは指数的に増えます。例えば各位置で 2 通り選べるので、全列挙すると最悪で \(2^{N}\) 近い探索になり、\(N \le 2\times 10^5\) では到底間に合いません。

そこで、「位置 \(i\) に到達する最小足跡数」を使って前から順に計算する動的計画法を使います。

アルゴリズム

DP 定義

[ dp[i] = \text{タイル } i \text{ に到達したときの足跡数の最小値} ]

到達方法は \(i-1\) から 1 歩、または \(i-2\) から 2 歩のどちらかなので、 [ dp[i] = A_i + \min(dp[i-1],\ dp[i-2]) \quad (i\ge 3) ]

初期条件はスタート地点を必ず踏むことに注意して - \(dp[1] = A_1\) - \(dp[2] = dp[1] + A_2\)（タイル 2 に行くには必ず 1→2 で踏む）

最後に答えは \(dp[N]\) です。

具体例（イメージ）

例えば \(A = [1,0,1,1]\)（足跡が残るタイルが 1,3,4）なら、 - 1→3→4 と進めば足跡は \(A_1+A_3+A_4 = 3\) - 1→2→4 と進めば足跡は \(A_1+A_2+A_4 = 2\) のように、DP はこの最小値を自動的に選びます。

計算量

• 時間計算量: \(O(N)\)（各 \(i\) で定数回の更新）
• 空間計算量: \(O(N)\)（\(dp\) 配列）

実装のポイント

• 「足跡が残るか」は \(H_i>0\) かつ \(D_i>0\) のときだけなので、先に配列 \(A\)（0/1）に変換すると DP が単純になります。

• \(N=2\) のような小さいケースがあるため、\(dp[2]\) の初期化は条件分岐して安全に行います。

• Python では \(dp\) を 1-indexed（長さ \(N+1\)）にして、配列 \(A\)（0-indexed）との対応を A[i-1] とすると実装ミスが減ります。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    H = list(map(int, input().split()))
    D = list(map(int, input().split()))

    A = [1 if (h > 0 and d > 0) else 0 for h, d in zip(H, D)]

    INF = 10**18
    dp = [INF] * (N + 1)  # 1-indexed
    dp[1] = A[0]
    if N >= 2:
        dp[2] = dp[1] + A[1]
    for i in range(3, N + 1):
        dp[i] = A[i - 1] + min(dp[i - 1], dp[i - 2])

    print(dp[N])

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。