F - XY Ladder LCS Editorial by ygussany
重要な観察として，最長共通部分列 (LCS) の長さが \(\displaystyle\left\lfloor\frac{2N}{3}\right\rfloor\) 以上となるような入れ替え方が必ず存在します． これは，入力文字列ペアを \(3\) 文字ずつと余りに区切って，各区間で以下を観察することで確認できます．
- 区間長が \(1\) のとき，異なる文字がペアになっている場合が最悪ケースで LCS 長は \(0\)．
- 区間長が \(2\) のとき，\(1\) 文字目が同じ文字のペアであればその時点で LCS 長は \(1\) 以上，\(1\) 文字目が異なる文字のペアであれば \(2\) 文字目と必ずマッチさせられるので LCS 長は \(1\) 以上．
- 区間長が \(3\) のとき，\(1\) 文字目か \(3\) 文字目が同じ文字のペアであれば区間長が \(2\) の場合に帰着されて LCS 長は \(2\) 以上，いずれも異なる文字のペアであれば双方を \(2\) 文字目と必ずマッチさせられるので LCS 長は \(2\) 以上．
なお，区間長が \(4\) のときは XXYY, YXYX のペアなどが最悪ケースで，どのように入れ替えても LCS 長は \(2\) となります．
上記の観察より，最適解において \(\displaystyle\left\lceil\frac{N}{3}\right\rceil\) より遠く離れた文字同士をマッチさせて LCS を作ることはありません． したがって，\(\mathrm{dp}(k, R) \ \ \left(0 \le k \le N,\ |R| \le \displaystyle\left\lceil\frac{N}{3}\right\rceil\right)\) を「入力ペアの \(k\) 文字目までの入れ替え方を確定させ，文字列 \(R\) を未マッチとして使える状態で残しながら作れる暫定辞書順最小 LCS 」として，これを \(k\) の昇順に計算する動的計画法 (DP) によりこの問題を解くことができます． \(R\) や \(\mathrm{dp}(k, R)\) を 64bit 整数に適切にエンコードしたり，遷移（ \(k\) に依らない部分）を前計算したりしておくことで，全体の計算量は \(\mathrm{O}(N 2^{\frac{N}{3}})\) になります．
$R$ と $\mathrm{dp}(k, R)$ のエンコード
X, Y からなる長さ $N$ 以下の文字列は，$2^{N+1}$ 未満の正整数を二進法で表現する bit 列と 1 対 1 に対応付けられます．
具体的には，X, Y をそれぞれ $1, 0$ と読み替えることにして，$1$ である最上位 bit を長さの表現として読み飛ばすことにすればよいです．
たとえば，XXY は $(1110)_2 = 14$ と，YY は $(100)_2 = 4$ と，空文字列は $(1)_2 = 1$ と対応します．
この表現における整数の大小関係は，元の文字列における「長さ」と「辞書順の逆順」に関する大小関係（「長さ」を優先）と等しいので，64bit 整数の通常の大小比較を行うだけで DP の遷移が計算できます．
遷移の前計算
上記のエンコードを行えば，$R$ は最大ケースでも $2^{18}$ 未満の正整数と対応付けられています． 未使用の文字を新たにマッチさせるときは手前にあるものから使って損はしないので，$2^{18}$ 未満の各正整数について，その二進法表現で最上位 bit の $1$ を読み飛ばしたときに初めて現れる $0, 1$ の位置をそれぞれ素朴に前計算しておくことで，各遷移を定数時間で計算できます． 前計算の計算量も $\mathrm{O}(N 2^{\frac{N}{3}})$ です．
posted:
last update: