NJPC2017 G - 交換法則

非想定っぽいなとは思った。

G: 交換法則 - NJPC2017 | AtCoder

解法

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
となる。判定に R が出てこないことが重要である。

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 倍程度の高速化が期待できる。