公式解説

aac003_d2 解説

By
yama_can

答えはたかだか NN 個であるため、 O(1)\mathcal O(1) 程度で候補が見つけられれば、全探索が可能です。
ちなみに、ほとんどの実装で M=2M=2 も含めることが出来ます。
例えば、以下の方針が考えられます。

  • A1G,AMGA^G_1, A^G_M を特別扱いする
  • 2≤i≤M−12\leq i\leq M-1 について、 (AiG,TiG)(A^G_i, T^G_i) と選択した SS の部分列は一致する必要があります。
  • 小課題3 では全探索が可能です。
  • Rolling Hash を用いた解法
    • (AiS,TiS)(A^S_i, T^S_i) を M−2M-2 個に渡って Rolling Hash すると、 O(N)\mathcal O(N) 個のハッシュができるので、これを比較するとよいです。
    • 普通にやると衝突させられる場合があるので、 TiST^S_i を座圧してランダムに変換するなどすると対処が可能です。
      • 計算量は O(N+M)\mathcal O(N+M) です。
    • 愚直な Rolling Hash を用いた解法
      • 文字 CC が KK 文字が連続する事による文字列を以下の式でもとめられます。
        • RH(C×K)=C×BK−1B−1 mod p\text{RH}(C \times K) = C \times \frac{B^K - 1}{B-1} \bmod p
        • BK1−1≡BK2−1(modp)B^{K_1} - 1\equiv B^{K_2} - 1 \pmod p を考える
        • フェルマーの小定理より、 K1≡K2(mod(p−1))K_1 \equiv K_2 \pmod{(p-1)} はこれを満たす
        • これは複数の mod でも制約下で合成が可能である
      • そのため、あまり使われない mod で処理したり、とても複数の mod を組み合わせることでこれが対策できます。
      • どこで Rolling Hash の値を評価するかを予め決めておくことで通常より簡潔な実装が可能です。
      • 計算量は O(N+M)\mathcal O(N+M) です。
  • Z-Algorithm を用いた解法
    • 先頭に (AiG,256+TiG)(A^G_i, 256 + T^G_i) を入れ、その後に (AiS,256+TiS)(A^S_i, 256 + T^S_i) を入れることで、確定的な一致判定が可能です。
    • AtCoder Library に入ってます！！
    • 計算量は O(N+M)\mathcal O(N+M) です。

テストケース生成

  • もうしたくないです