AtCoder Regular Contest 087 E - Prefix-free Game - アルゴリズマーの備忘録

あと少しでコンテスト中に解けていたので悔しい…

問題概要

文字列の集合sに文字列をAliceとBobが交互に追加していく。ただし、文字列はl文字以下で、sのどの文字列も集合内の他の文字列のprefixとなってはいけない。
文字列を追加できなくなったら負けというルールがあるとき、どちらが勝つか。

解説

Trie木がAtCoderの解説として取り上げられていますが、少し実装が面倒な別解っぽい何かを。

例えば、sに0100と0101があるとき、この2つの文字列はまとめて010と扱って問題ありません。この性質を利用して、集合の要素数を徐々に減らしていきます。が、上手くやらないと簡単にTLEしてしまうので、

「先に文字数→文字列の比較」というルールの下でsをソート
ソート後、文字数の多いものから文字数を1減らしていく

という工夫が必要です。1つ目に関しては蟻本のSAを知っていれば特に問題無いかと。2つ目ですが、見ている文字列の末尾の01を入れ替えた文字列を探します。これは、存在するなら先に1で終わる文字列を見るはずなので、必ずi-1に存在するはず。存在するなら、そのまま片方の末尾を消して正しい場所へinsertし、もう片方は集合から削除します。存在しないなら、その文字列の末尾を消して正しい場所へinsertするのですが、この際に存在しない場所にはプレイヤーが文字列を追加する必要があるので、ここにゲーム要素があります。

プレイヤーが文字列を追加するとき、木の枝を切っていくイメージ（これは昨年のTSGの部誌にそれっぽいことが書いてある）でゲームが進められます。そのため、各高さ毎の二分木のgrundy数を求めたら後はxorしていくだけです。が、この計算が手作業でやると軽く死にます。コンテスト終了5分前に私はこの計算を手計算で行い始め、高さ3まで計算して偶奇で分ければ良さそうと判断しWAしたので、ちゃんとプログラム組んで確かめましょう…

計算量は文字数の合計をSとしてO(SlogN)くらい？よく分かりません。

Submission #1883066 - AtCoder Regular Contest 087

vector<string> s;

bool com(string i, string j) {
    if (i.length() != j.length()) return i.length() < j.length();
    else  return i < j;
}

int findstr(int i) {
    s[i][s[i].size() - 1] = '1' + '0' - s[i][s[i].size() - 1];
    if (i > 0 && s[i] == s[i - 1]) {
        s[i][s[i].size() - 1] = '1' + '0' - s[i][s[i].size() - 1];
        return i - 1;
    }
    if (i + 1 < s.size() && s[i] == s[i + 1]) {
        s[i][s[i].size() - 1] = '1' + '0' - s[i][s[i].size() - 1];
        return i + 1;
    }
    s[i][s[i].size() - 1] = '1' + '0' - s[i][s[i].size() - 1];
    return -1;
}

int main() {
    int n; ll l;   cin >> n >> l;
    s.resize(n);
    rep(i, n)   cin >> s[i];
    sort(s.begin(), s.end(), com);
    ll grundy = 0;
    while (s.size() > 0) {
        int i = s.size() - 1;
        int idx = findstr(i);
        if (idx != -1) {
            s[idx].pop_back();
            s.erase(s.begin()+i);
        }
        else {
            s[i].pop_back();
            ll x = l - s[i].size();
            grundy ^= x - (x&(x - 1));
            idx = i;
        }
        if(idx>0) {
            string tmp = s[idx];
            s.erase(s.begin() + idx);
            int left = 0, right = idx;
            rep(t, 20) {
                int mid = (left + right) / 2;
                if (s[mid].size() < tmp.size())    left = mid;
                else if (s[mid].size() > tmp.size()) right = mid;
                else if (s[mid] < tmp)   left = mid;
                else if (s[mid] > tmp)   right = mid;
            }
            s.insert(s.begin() + right, tmp);
        }
        else if (s[idx] == "")   break;
    }
    cout << (grundy == 0 ? "Bob" : "Alice") << endl;
    return 0;
}