概要

廊下の各タイルにはほこりがあり、高橋君がタイルを踏むとほこりが減ります。高橋君はタイル1からスタートしてタイルNを目指し、1回の移動で1マスまたは2マス進めます。高橋君が通ったことでほこりが減った（足跡が残った）タイルの数を最小にするような経路を求めます。

考察

この問題の本質は、「どのタイルを踏むか」によって足跡の数が変わるという点です。各タイル \(i\) において、以下の場合にのみ足跡が残ります：

• 初期のほこり \(H_i > 0\) かつ 減少量 \(D_i > 0\)

これはタイルの性質であり、高橋君がそのタイルを踏んだかどうかに関わらず、条件を満たさないタイルは絶対に足跡を残しません。したがって、事前に各タイルが「足跡を残す可能性があるか」を判定しておくことができます。

次に、高橋君は経路を選ぶことで、どのタイルを踏むかをある程度選ぶことができます。例えば、あるタイル \(i\) が足跡を残す場合、そのタイルを通らない経路を選ぶことで足跡を避けることが可能です（ただし、最終的にタイル \(N\) に到達しなければならない制約があります）。

このように「コストがかかる頂点を通るかどうかを選ぶ最短経路問題」として考えることができます。ここでいう「コスト」とは、足跡が残るタイルの数です。

素朴な方法としては、全経路を探索する方法がありますが、タイルの数 \(N\) は最大 \(2 \times 10^5\) まであるため、再帰や全探索では時間内に終わりません。そこで、動的計画法（DP）を用いて効率的に解きます。

アルゴリズム

動的計画法（DP）を用います。

ステップ

1. 前処理： 各タイル \(i\) に対して、足跡が残るかどうかを判定します： $\( \text{footprint}[i] = \begin{cases} 1 & \text{if } H_i > 0 \text{ and } D_i > 0 \\ 0 & \text{otherwise} \end{cases} \)$

2. DPテーブル定義： $\( dp[i] := \text{タイル} i \text{に到達した時点での足跡の最小数} \)\( ただし、タイル \)i\( 自体を踏むので、\)\text{footprint}[i]$ を加算します。

3. 初期化：

   • \(dp[0] = \text{footprint}[0]\) （タイル1からスタート）

4. 遷移： 各 \(i = 2, 3, ..., N-1\) に対して： $\( dp[i] = \min(dp[i-1], dp[i-2]) + \text{footprint}[i] \)$ これは「1つ前から来る」か「2つ前から来る」かのうち、足跡が少ない方を選ぶということです。

5. 答え： \(dp[N-1]\) が求める答えです。

例

入力例：

5
1 0 2 3 0
1 1 2 1 1

• footprint配列：[1, 0, 1, 1, 0]
• DP遷移：
  • 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

→ 答え：2

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• footprintの計算は前処理で行い、DPテーブルの更新時に利用することで効率化します。
• dpテーブルは初期化時にインデックスエラーにならないよう注意（N=2の場合など）。
• 入力を高速に読み込むために sys.stdin.read を使用しています。

## ソースコード

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

---

この解説は qwen3-coder-480b によって生成されました。