概要

数列 \(A\) から順序を保って要素を選び、パターン数列 \(P\) と完全に一致する部分列を作る方法の数を、動的計画法（DP）で効率的に数え上げる問題です。

考察

問題の理解

例えば、\(A = [1, 2, 1, 2]\)、\(P = [1, 2]\) の場合を考えます。 - \((A_1, A_2) = (1, 2)\) → 一致 ✓ - \((A_1, A_4) = (1, 2)\) → 一致 ✓ - \((A_3, A_4) = (1, 2)\) → 一致 ✓

このように、位置が異なれば別の方法として数えるので、答えは \(3\) 通りです。

素朴なアプローチの問題点

全ての部分列を列挙すると、長さ \(N\) の数列から長さ \(K\) の部分列を選ぶ方法は最大 \(\binom{N}{K}\) 通りあります。\(N = 10^5\)、\(K = 100\) の場合、これは天文学的な数になり、TLE（時間超過）は確実です。

解決策：動的計画法

「\(P\) の先頭 \(j\) 個と一致する部分列が何通りあるか」を順次計算していきます。\(A\) の各要素を1つずつ見ていき、それが \(P\) のどの位置にマッチするかで場合分けします。

アルゴリズム

DPの定義

\(dp[j]\) = 数列 \(A\) の現在までの要素を使って、\(P\) の先頭 \(j\) 個と一致する部分列を作る方法の数

初期状態

• \(dp[0] = 1\)（空の部分列は1通り）
• \(dp[1], dp[2], \ldots, dp[K] = 0\)

遷移

\(A\) の各要素 \(A[i]\) について： - もし \(A[i] = P[j]\) ならば、\(dp[j+1]\) に \(dp[j]\) を加算する - つまり「\(P\) の先頭 \(j\) 個が揃っている状態」から「\(A[i]\) を選んで \(j+1\) 個揃った状態」に遷移

更新順序の重要性

逆順（\(j = K-1\) から \(j = 0\)）に更新する必要があります。

順方向に更新すると、同じ \(A[i]\) を複数回使ってしまう可能性があります。例えば、\(dp[0] \to dp[1] \to dp[2]\) と更新すると、1つの \(A[i]\) で \(P[0]\) と \(P[1]\) の両方にマッチしたことになってしまいます。

逆順なら、\(dp[j+1]\) を更新する時点で \(dp[j]\) はまだ古い値（\(A[i]\) を使う前の値）なので、正しく計算できます。

具体例での動作

\(A = [1, 2, 1]\)、\(P = [1, 1]\) の場合：

処理	\(dp[0]\)	\(dp[1]\)	\(dp[2]\)
初期	1	0	0
\(A[0]=1\) を処理	1	1	0
\(A[1]=2\) を処理	1	1	0
\(A[2]=1\) を処理	1	2	1

答えは \(dp[2] = 1\)（位置 \(0\) と位置 \(2\) の組み合わせのみ）

計算量

• 時間計算量: \(O(N \times K)\)
  • \(A\) の各要素（\(N\) 個）について、\(P\) の各位置（\(K\) 個）をチェック
• 空間計算量: \(O(K)\)
  • DP配列のサイズ

実装のポイント

1. 逆順ループ: for j in range(K - 1, -1, -1) で \(j\) を大きい方から小さい方へ処理することで、同じ要素の重複使用を防ぐ

2. MOD演算: 答えが非常に大きくなるため、加算のたびに \(10^9 + 7\) で割った余りを取る

3. 1次元DPで十分: 2次元配列 \(dp[i][j]\)（\(A\) の \(i\) 番目まで見て \(P\) の \(j\) 個一致）を使わなくても、逆順更新により1次元で実現可能

   ソースコード

def solve():
    MOD = 10**9 + 7
    
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    P = list(map(int, input().split()))
    
    # dp[j] = Pの最初のj個と一致する部分列の数
    # dp[0] = 1 (空の部分列)
    dp = [0] * (K + 1)
    dp[0] = 1
    
    for i in range(N):
        # A[i]を使って更新
        # 逆順に更新しないと同じA[i]を複数回使ってしまう
        for j in range(K - 1, -1, -1):
            if A[i] == P[j]:
                dp[j + 1] = (dp[j + 1] + dp[j]) % MOD
    
    print(dp[K])

solve()

---

この解説は claude4.5opus によって生成されました。