ABC 130 E - Common Subsequence

• 問題
• AC

共通部分列で末尾が$S_x$かつ$T_y$であるものの総数を$f(x, y)$とすると、求める数は（空の文字列を含めるので）$1+\sum_{1\le x \le N, 1\le y \le M}f(x, y)$である。$f$の漸化式は

$f(x,y) = \begin{cases} 0 & \qquad (S_x \neq T_y) \\ \sum_{i<x, j<y} f(i, j) + 1 & \qquad (S_x = T_y) \end{cases}$

と書けるが、このままDPすると間に合わないので累積和$S(x, y) = \sum_{1\le i \le x, 1 \le j \le y}f(i, j)$を使って遷移する。

$f(x,y) = S(x-1, y-1)+1 \qquad (S_x = T_y)\\ S(x,y) = S(x-1, y) + S(x, y-1) - S(x-1, y-1) + f(x,y)$

だから、$S$について整理すると

$S(x,y) = \begin{cases} S(x-1, y)+S(x, y-1)-S(x-1, y-1) & \qquad (S_x \neq T_y) \\ S(x-1, y) + S(x, y-1) +1 & \qquad (S_x = T_y) \end{cases}$

２次元累積和上でDPすればよさそうというのは早い段階で検討がついたが、初めてだったせいか式を立てている最中にoff-by-oneの誤りをやって時間を消費した。そのままハマってしまう危険を感じたのでひとまず２次元BITを試したら通って事なきを得た。¹

この問題に関しては、２次元累積和の遷移の式を陽に覚えていれば済むことではあったので、知識が増えたと思っておく。ただ、0-based、半開区間で処理するとき、累積和絡みの考察でよく混乱しているのも確かなので、一度整理したい。

---

1. $\log^2n$が付くので危なそうと思ったが、定数倍に気をつければ600msくらいで済んでいる。 ↩︎