解説

実装例

まずは実装例をご覧ください。他プログラムと比べて非常にシンプルで、かつ高速なプログラムとなりました。

実際、少し修正することで shortest を大幅に更新できました。

https://atcoder.jp/contests/abc433/submissions/76408628 (shortest)

#include <bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
int f[1 << 20];
int main() {
    int t; cin >> t;
    while(t--) {
        string s; cin >> s;
        auto sa = suffix_array(s);
        auto lc = lcp_array(s, sa);
        int n = s.size();
        for(int i = 0; i < n; i ++) f[i] = (n - sa[i]) & 1;
        dsu uf(n);
        vector<vector<int>> task(n);
        for(int i = 0; i < n - 1; i ++) task[lc[i]].push_back(i);
        for(int i = n - 1; i >= 0; i --) {
            for(int j : task[i]) {
                int x = uf.leader(j), y = uf.leader(j + 1);
                if(i & 1) f[x] &= f[y];
                else f[x] |= f[y];
                f[y] = f[x];
                uf.merge(x, y);
            }
        }
        cout << (f[uf.leader(0)] ? "Alice" : "Bob") << endl;
    }
}

概要

部分文字列全体を頂点とする Trie を考えると、このゲームは Trie 上のゲームになります。しかし、部分文字列は \(O(N^2)\) 個存在するため、そのまま Trie を構築することはできません。

そこで、Trie を陽に作る代わりに Suffix Array と LCP を用いて暗黙的に処理します。

Suffix Array 上では、ある文字列を prefix に持つ suffix は必ず連続区間になります。また、その区間は LCP の値を大きい方から見ていくことで順に構築できます。

初期状態

各 suffix を単独で考えると、対応する Trie は一本道になります。

一本道では葉まで残っている手数の偶奇だけで勝敗が決まるため、各 suffix の勝敗はその suffix の長さの偶奇だけで初期化できます。

LCP の大きい順に処理する

LCP が \(x\) の隣接する 2 つの suffix は、長さ \(x\) の prefix を共有しています。

そこで、LCP の値ごとに対応する隣接ペアをまとめておき、LCP の大きい方から順に処理します。

ある長さで複数の suffix が同じ prefix を共有する場合、それらを 1 つの連結成分として扱います。連結成分の勝敗は、ゲーム DP の遷移に従って統合します。

深さ（現在見ている文字列長）の偶奇によって遷移は

• 偶数長なら OR
• 奇数長なら AND

となるため、その規則に従って連結成分の勝敗を更新していきます。

すべての長さについて処理を終えると、空文字列に対応する連結成分が得られ、その勝敗が答えになります。

UnionFind の適用

UnionFind を用いれば、「現在属している連結成分を取得する」「2 つの連結成分を結合する」という操作だけで区間管理ができます。勝敗も各連結成分の代表に持たせればよいため、実装を非常に簡潔にできます。

このような 区間や集合を順次マージしていく問題では UnionFind が非常に有効です。

計算量

Suffix Array と LCP の構築が \(O(N)\)、UnionFind の操作がならし \(O(N\alpha(N))\) なので、全体の計算量は

\[ O(N\alpha(N)) \]

となります。

https://atcoder.jp/contests/abc433/submissions/71178302