NJPC2017 G - 交換法則
非想定っぽいなとは思った。
解法
dp[L,R]:=[L,R)の文字列を構成可能かどうか
という区間 DP をすれば O(n3) で解ける。
dp[L,R]=dp[L,M] and dp[M,R] and s[L..M)<=s[M..R)
という漸化式になる。s[L..M)≦s[M..R)の判定は suffix array と LCP を用いればよい。
s[i..] の順位を rank[i] とする。このとき s[L..M)≤s[M..R) となる条件は
- rank[L]≤rank[M]
- rank[L]>rank[M] かつ lcp( s[L..M), s[M..R) )=M-L
- rank[L]≤rank[M]
- rank[L]>rank[M] かつ lcp( s[L..), s[M..) )≥M-L
suffix array と LCP は高度なアルゴリズムを使わなくても O(n2 log n) で計算できる。
ok[i][j]:=s[i..j)<=s[j..)
ldp[L][i]:=dp[L][i]
rdp[R][i]:=dp[i][R]
という bitset を作っておけば、
dp[L][R]=(ldp[L] & rdp[R] & ok[L]) != 0
で計算できる。計算量は O(N3) ではあるが、ビットごとに並列して計算できるため 64 倍程度の高速化が期待できる。