Day 158-Q4 | 行ビット列Sの更新

問題

英小文字からなる文字列 $A$（長さ $N$）と $B$（長さ $M$）が与えられる。$A$ と $B$ の 最長共通部分列（LCS）の長さ を求めよ。部分列は連続でなくてよい。

入力形式

A
B

制約

#	条件
1	$1 \le N, M \le 5 \times 10^4$
2	$A, B$ は英小文字のみ

入出力例

入力例1

abcbdab
bdcaba

出力例1

（例: bcba、bdab など。長さ 4）

参考: EDPC F「LCS」（https://atcoder.jp/contests/dp/tasks/dp_f 、2026-09-23 参照）は $N,M \le 3000$ で復元まで求める。本問は長さのみだが $N \cdot M = 2.5\times10^9$ で、通常の DP は Python では到底間に合わない。

概念図：行ビット列Sの更新

ヒント（クリックで段階的に開示）

ヒント1（方向性）

LCS の DP 表 $L[i][j]$ は、同じ行で隣り合うマスの差が 0 か 1 しかない。「差が 0/1 しかない行」は ビット列1本 で表せる。行の更新をビット演算でまとめてできないか。

ヒント2（アプローチ）

$A$ の各文字 $c$ について「$A$ のどの位置が $c$ か」のビットマスク $M_c$ を作る。$B$ の文字を1つずつ読み、行ビット列 $S$ を更新する。このとき、DP の「左から伝わってくる +1」は 2進数の足し算の繰り上がり がちょうど同じ伝わり方をする。

ヒント3（誘導）

Hyyrö (2004) の形:

S = (1 << N) - 1            # 1 のビット = まだ「使っていない」位置
for b in B:
    U = S & M[b]
    S = ((S + U) | (S - U)) & full
LCS = N - popcount(S)

模範解答 (Python)

模範解答を表示する（まず自力で解いてから）

import sys


def main():
    data = sys.stdin.read().split()
    A, B = data[0], data[1]
    n = len(A)
    full = (1 << n) - 1

    # M[c] : A の中で文字 c が現れる位置（ビット i = A[i]）
    M = {}
    for i, ch in enumerate(A):
        M[ch] = M.get(ch, 0) | (1 << i)

    S = full
    for ch in B:
        m = M.get(ch)
        if m is None:          # A に無い文字は行を変えない
            continue
        U = S & m
        S = ((S + U) | (S - U)) & full

    print(n - S.bit_count())   # Python 3.10+（それ以前は bin(S).count("1")）


main()

計算量: $O(M \cdot \lceil N / w \rceil)$。$w$ は CPython の多倍長整数の1桁（リム）のビット幅（通常 30）。$N=M=5\times10^4$ で約 $8.3\times10^7$ リム操作だが、それぞれが C のループ内で行われる。

Step-by-Step 解説

1DP の行差分は 0/1

$L[i][j] = $「$A$ の先頭 $i$ 文字と $B$ の先頭 $j$ 文字の LCS」。$L[i][j] - L[i-1][j] \in \{0, 1\}$（1文字増やして LCS が2以上増えることはない）。したがって「$B$ の $j$ 文字目まで読んだ時点の行」は、差分ビット列 $V_j$（ビット $i$ = $L[i+1][j]-L[i][j]$）で完全に表せる。本解の $S$ は $V_j$ の反転（1 = 差分 0）で、$\mathrm{LCS} = N - \mathrm{popcount}(S)$。

21文字読むとき何が起きるか

$B$ の文字 $b$ を読むと、$A$ 中の $b$ の位置で「新しいマッチ」が起き得る。各「まだ使っていない（$S$ のビットが 1 の）連続区間」で、一番下（$A$ の前方）にあるマッチ位置 を 1 つだけ使う（0 にする）のが最適で、それより上の $S$ の区間は1つ上に「押し上げ」られる。

$U = S \mathbin{\&} M_b$ : 使える候補
$S + U$ : 候補のビットに 1 を足すと、その上に続く 1 の連なりを繰り上がりが駆け抜け、連なりの終わりで止まる。これが「区間ごとに一番下のマッチだけ採用」を一括で行う
$| (S - U)$ : 足し算で消えすぎた（候補でないのに 0 になった）ビットを戻す

3入力例で追う（$A$=abcbdab, ビット0 が先頭）

左端をビット6・右端をビット0 として $M_a$=0100001（位置0,5）、$M_b$=1001010（位置1,3,6）、$M_c$=0000100、$M_d$=0010000。最初の $b$ で $U = S \mathbin{\&} M_b$ に位置1,3,6 が立つが、$S$ は全部 1 の1区間なので、足し算の繰り上がりにより「位置1だけ 0」になる → LCS 1。以降 6 文字を処理すると popcount$(S)=3$、$7-3=4$。

4なぜ Python で速いのか

+・-・&・| はすべて CPython の多倍長演算で、$N$ ビットを約 $N/30$ 桁のリム配列として C のループで処理する。Python レベルのループは $M$ 回だけ。実測で $N=M=3000$ の DP が 0.586 秒、ビット並列が 0.002 秒（約 290 倍）。

迷った他案と採らなかった理由

案	計算量	採否	理由
通常の 2 次元（1 行ずつ持つ）DP	$O(NM)$	比較用のみ	$N=M=3000$ で 0.586 秒（実測）。$5\times10^4$ では約 280 倍の $\approx 160$ 秒と見積もられ不可（導出: $NM$ 比 277.8 倍）
Hunt–Szymanski（マッチ対を LIS に帰着）	$O((r + N)\log N)$、$r$ = マッチ対の数	不採用	英小文字 26 種のランダム文字列では $r \approx NM/26 \approx 10^8$ で遅い。文字種が非常に多い（$r$ が小さい）入力に変わったらこちら
Myers の O(ND) 差分アルゴリズム	$O((N+M)D)$、$D$ = 編集距離	不採用	$A$ と $B$ がほとんど同じ（diff ツールの用途）なら最速だが、ランダム入力では $D$ が大きく利点がない。本シリーズ Day099 Q2 の Myers ビットベクトル法は編集距離の計算で、本問の LCS 用の加算トリックとは更新式が異なる
NumPy で DP を行ベクトル化	$O(NM)$	不採用	行内の依存（左からの伝播）が逐次なので素直にはベクトル化できない。ビット並列はこの依存を「繰り上がり」に肩代わりさせている点が本質
ビット並列（本解）	$O(M N / w)$	採用	実装 10 行、標準ライブラリのみ

よくあるミス

ミス	原因	正しい書き方
`& full` を付け忘れる	$S+U$ の繰り上がりがビット $N$ より上へ漏れる	毎回 `& full` で $N$ ビットに切る（付けないと popcount が狂う）
`U = S & M[b]` を省いて `U = M[b]` とする	「すでに使った（0 になった）位置」も候補に入れてしまう	候補は必ず $S$ と $M_b$ の共通部分。省くと入力例1で 4 ではなく 2 が出る（本セッションで実測）
ビットの向きを逆にする（$A[0]$ を最上位に）	繰り上がりは下位→上位にしか伝わらない	$A$ の先頭を最下位ビットに置く（DP で $i$ が増える方向 = 繰り上がりの方向）
`bit_count()` が無い環境	Python 3.9 以前	`bin(S).count("1")`
復元（LCS 文字列そのもの）まで求めようとする	長さしか持たないビット列から経路は戻せない	復元が要るなら Hirschberg（Day090 Q3・Day141 Q1）で $O(NM)$ 時間・$O(N)$ 空間

次のステップ

発展1: 「$B$ の全ての部分文字列 $B[l..r]$ と $A$ の LCS」を一括で求める semi-local LCS（Tiskin の seaweed 法）
発展2: ランダムな 4 文字 DNA 列で LCS/長さが約 0.654 に収束する（Chvátal–Sankoff 定数）ことを、長さを変えて実測してみる
扱わなかった範囲: LCS の文字列そのものの復元、重み付き LCS

検証ログ（本セッションで実行した数値）

入力例1: ビット並列 4、DP 4 で一致
ランダムテスト: 文字種 2・3・4・26 種、長さ 0〜30 の組 2000 件で DP と比較 → 不一致 0 件（空文字列を含む）
性能（実測）: $N=M=3000$（4 文字種）でビット並列 0.002 秒 / DP 0.586 秒、LCS はどちらも 1947
性能（実測）: $N=M=5\times10^4$（4 文字種）でビット並列 0.330 秒、LCS = 32678（比 0.6536。4 文字ランダム列の Chvátal–Sankoff 定数の既知の推定値 ≈ 0.654 と整合）
検証スクリプト: スクラッチパッドの q4.py（上記は実行結果の転記）

自己評価

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

Day 158-Q4 — ビット並列 LCS（Allison–Dix / Hyyrö の加算トリック）

問題