♥沙耶花の備忘録♥

ARC058-F 文字列大好きいろはちゃん

解法
提出コード
終わりに

公式解説とは違うやり方れふ.

$K\le 10^4$ で $O(K^2)$ は余裕っ(素振り)

解法

$dp[i$ ]: $i$ 文字の, 辞書順最小の文字列を作るとして, 最後に使う文字列のインデックス(複数ある場合, 最小のもの)

これを順に求め, 最後に復元しまふ.

$dp[i$ ]からの遷移としてvalidなものは, 次の条件を満たすものれふ.

使う文字列のインデックスが $dp[i$ ]より大きい
その遷移をした結果, 長さ $K$ の文字列が作れなくなるということが無い
他のvalidな遷移に対応する文字列と比較して, その遷移によって生成される文字列が辞書順で大きくなってしまわない

2に違反する遷移は, あらかじめ部分和DPをしておけば検出できまふ.

3に違反する例を挙げまふ.

$N=4, K=4$ , $S = \{"abcd", "ab", "d", "d"\}$

この時, $dp[2] =1$ となりまふが, そこから $dp[3]=2$ などとする遷移はinvalidれふ.

( $"abcd"$ に対して $"abd"$ は辞書順で大きいため)

このような遷移を弾くには, この例における $"abcd"$ のように, 辞書順最小の可能性のある文字列のうち最も先まで文字を確定させている文字列を記憶し, 比較する必要がありまふ.

また, 次のようなケースがありまふ.

$N=4, K=4$ , $S = \{"abcd", "ab", "a", "d"\}$

このようなケースでは, $dp[3]=2$ を求めた瞬間に, $dp[0]$ から求めた $dp[4]=0$ がinvalidになりまふ. 辞書順最小の可能性のある文字列のうち最も先まで文字を確定させている文字列が $"abcd"$ から $"aba"$ に更新され, それ以前に求めた遷移が正しいと限らなくなった形れふ. このようなケースは, $dp[i]$ を求めた直後に $dp[i+1]$ 以降を $O(K)$ かけて潰せば良いれふ.

以上の解法を実現するためには, 文字列 $a$ の $b$ 文字目以降と文字列 $c$ の $d$ 文字目以降に対し, 先頭から何文字共通しているかや, 辞書順でどちらが小さいかを高速に求める必要がありまふ. これらは, Suffix Array, およびそのLCPを求めてやれば $O(1)$ で達成できまふ.

参考

niuez.hatenablog.com

提出コード

終わりに

金diffれふが, 時間をいくらでもかけてよければ通しやすいタイプ……？