# **[2021/01/07 shichifuku01](https://codeforces.com/gym/311129)** # **E. Erase Subsequences** $S$ の distinct な部分列 $2$ つで $T$ を作れるか判定する. 制約をよくみてみると, $1$ ケース $O(|s|^4)$ が間に合う. DP 以外でうまくできそうもないので, 当然 DP をする (は?). まず $T$ を $2$ つに分ける位置を決め打つ. ```cpp bool DP[S の i 文字目までみた][T の前半の j 番目まで一致][T の後半の k 番目まで一致] ``` としたくなるところだが, これだとメモリが $400^3$ で足りないので, ```cpp int DP[S の i 文字目までみた][T の前半の j 番目まで一致] = T の後半の一致の最大インデックス ``` としてあげることで無事 AC が得られる. # **F. Number of Components** グリッドがあり, 各クエリごとに $1$ つのマスの色が変化するので, 毎回変化後の (色が同じ隣接したマスたちを連結成分としたときの) 連結成分数を求める. よくみると, 色の数字は広義単調増加で, しかも $O(\alpha(N) \times (NMC + Q))$ が間に合う. 色が変化するタイミングで Union Find を初期化することを考えれば, 現在の色を $c$ として - 色 $c$ のマスは前からみるとただ増えていくだけなので Union Find で求まる. - 色 $c$ 未満のマスは後ろからみるとただ増えていくだけなので色の管理に気をつけつつ Union Find で求まる. 連結成分数は,マスの色が変化する度に $1$ を足して, Union Find の Unite 関数で True が帰ってきた分だけ減らすと $O(1)$ で正しく求まる. 定数倍重めの (アッカーマンの逆関数) $\times 10^7$ で TL がかなり厳しい.