Day 147-Q3 | Four Russians法（四露人法）

問題

2つの文字列 $A,B$（アルファベット `A`,`C`,`G`,`T` の4種類）が与えられる。DPテーブルを $t\times t$ のブロックに分割して処理する方式で、$A,B$ の最長共通部分列（LCS）の長さを求めよ。

通常のLCS漸化式:

$$dp[i][j] = \begin{cases} dp[i-1][j-1]+1 & (A_i=B_j) \\ \max(dp[i-1][j],dp[i][j-1]) & (A_i\ne B_j) \end{cases}$$

この計算を $t\times t$ ブロック単位で処理し、各ブロックのキー = (左境界の差分列, 上境界の差分列, ブロックのA文字, ブロックのB文字) が過去に出現していれば「全く同じ内部計算になるブロック」である。同じキーが何回出現したかは、Four Russians法が本来 $O(1)$ の表引きに置き換えられる箇所の目安になる。本問では正しさ優先で値は直接計算する簡略版とし、LCSの長さのみを出力する。

入力形式

t
A
B

制約

$1 \le t \le 4$

$A,B$ は A,C,G,T からなる

$1 \le |A|,|B| \le 64$

$|A|,|B|$ はともに $t$ の倍数

入出力例

入力例1

2
ACGTAC
AGCATC

出力例1

概念図：DPテーブルの2×2ブロック分割

ヒント（段階的開示）

ヒント1（方向性）

通常のLCS DPは1マスずつ埋めれば$O(NM)$。「$t\times t$のブロックをまとめて1回の処理単位にする」という発想の転換がFour Russians法の出発点。依存関係の順序さえ守れば1マスずつ埋めるのとブロック単位で埋めるのは数学的に同じ計算になる。

ヒント2（アプローチ）

LCSのDPは隣接マスの差が$0$か$1$（単調性）。この性質により、ブロックの「境界の絶対値」ではなく「境界の差分パターン」だけで内部計算結果が決まる。ブロックが担当する$A,B$の$t$文字が同じであれば全く同じ内部計算になる——これがキャッシュキーの正体。

ヒント3（誘導）

def lcs_blocked(A, B, t):
    N, M = len(A), len(B)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    seen_keys = set()
    for bi in range(N // t):
        for bj in range(M // t):
            i0, j0 = bi * t, bj * t
            left_diffs = tuple(dp[i0+k][j0]-dp[i0+k-1][j0] for k in range(1,t+1))
            top_diffs = tuple(dp[i0][j0+k]-dp[i0][j0+k-1] for k in range(1,t+1))
            key = (left_diffs, top_diffs, A[i0:i0+t], B[j0:j0+t])
            seen_keys.add(key)
            for di in range(1, t+1):
                for dj in range(1, t+1):
                    i, j = i0+di, j0+dj
                    if A[i-1] == B[j-1]:
                        dp[i][j] = dp[i-1][j-1] + 1
                    else:
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[N][M]

模範解答 (Python)

import sys

def lcs_blocked(A, B, t):
    N, M = len(A), len(B)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    seen_keys = set()
    hit_count = 0

    for bi in range(N // t):
        for bj in range(M // t):
            i0, j0 = bi * t, bj * t
            left_diffs = tuple(dp[i0 + k][j0] - dp[i0 + k - 1][j0] for k in range(1, t + 1))
            top_diffs = tuple(dp[i0][j0 + k] - dp[i0][j0 + k - 1] for k in range(1, t + 1))
            block_a = A[i0:i0 + t]
            block_b = B[j0:j0 + t]
            key = (left_diffs, top_diffs, block_a, block_b)
            if key in seen_keys:
                hit_count += 1
            else:
                seen_keys.add(key)

            for di in range(1, t + 1):
                for dj in range(1, t + 1):
                    i, j = i0 + di, j0 + dj
                    if A[i - 1] == B[j - 1]:
                        dp[i][j] = dp[i - 1][j - 1] + 1
                    else:
                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[N][M], hit_count


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    A = data[1].decode()
    B = data[2].decode()

    lcs_len, hit_count = lcs_blocked(A, B, t)
    print(lcs_len)


main()

Step-by-Step 解説

1ブロック単位への再構成
行を1本ずつ埋めるのではなく、$t\times t$ブロックを左上から行優先で埋める。依存先が常に既に埋め終えたブロックにあることが保証されれば結果は通常のDPと一致する。

2境界差分列というキー設計
隣接マスの差は$0$か$1$のみ。左境界・上境界それぞれ$t$個の差分は$2^t$通りずつ、文字は$4^t$通りずつでキーの種類数は定数個に収まる。

3キャッシュヒットの意味
同一キーの再出現は「全く同じ内部計算になるブロック」を意味する。実際のFour Russians法ではここを$O(1)$の表引きに置換し全体を$O(NM/t)$程度、$t=\Theta(\log N)$なら$O(NM/\log N)$に落とす。

4正しさの検算
依存順序を守る限りブロック単位でも通常の行優先DPと完全一致する。$A=$ACGTAC, $B=$AGCATC を手計算すると$dp[6][6]=4$で一致する。

よくあるミス

ミス	原因	正しい書き方
ブロック処理順を列優先にしてしまう	依存先マスが未計算の状態で参照してしまう	行優先（biを外側、bjを内側）で左上から処理する
境界差分の符号を逆にする	LCSのDPは単調非減少なのに差が負になり気づく	`dp[i0+k][j0]-dp[i0+k-1][j0]`の順で差分を取る
キーに絶対値のdpそのものを含める	平行移動しただけの同一パターンを別扱いしキャッシュが効かない	絶対値ではなく差分列をキーにする
tが\|A\|や\|B\|の約数でない入力を想定する	端数ブロックの扱いが定義から漏れる	制約でtが両方の長さを割り切ることを前提にする
大きいアルファベットでも有効だと誤解する	キー種類数がアルファベットサイズのt乗で増える	本手法はアルファベットが小さい場合に特に有効と踏まえる

次のステップ

発展: `hit_count`を出力に加え、$t=1,2,3,4$でキャッシュヒット率がどう変化するか実測せよ。
次回予告: Bloom Filter（ブルームフィルタ・複数ハッシュ関数による確率的membership判定）

自己評価

完全理解おおむね理解要復習

Day 147-Q3 — Four Russians法（四露人法・LCSのブロック単位高速化）

問題