ABC209-E Shiritori - zawatinはてなブログ

問題概要
制約
ゲームの言い換え
言い換えたゲームを観察する
この解析には名前がついている
提出コード

問題概要

https://atcoder.jp/contests/abc209/tasks/abc209_e

$N$ 個の文字列 $S_{i}$ が与えられる。高橋くんと青木くんが以下のルールの元しりとりをする

高橋君が先手で、交互に文字列を言う
与えられた文字列のいずれかと一致する文字列しか言うことができない
言う文字列のPrefix3文字は前の人が言った文字列のSuffix3文字と一致していなければいけない
すでに言われている文字列でも言うことができる

高橋くんが初手で $S_{i}$ を言ったあと両者が最適に行動する時、どちらが勝つかまたはしりとりが永遠に終わらないか判定しなさい。 $i = 0, 1, 2, \dots, N$ についてこれを解きなさい。

制約

$1\ \le\ N\ \le\ 2\times 10^{5}$
与える各文字列の長さは $3$ 以上 $8$ 以下

ゲームの言い換え

とりあえず各文字列についてPrefix3文字とSuffix3文字以外はどうでも良いです。

なのでPrefix3文字、Suffix3文字を頂点としたグラフを考えて各文字列についてPrefix3文字からSuffix3文字に向かって辺を張ります。

入力例１だと下の画像のような感じです。

めちゃくちゃ小さいですが、よく目を凝らすと自己ループ以外は矢印の三角がついてます(有向グラフです)

~~Google図形描写、自己ループの書き方分からんかった~~

このような有向グラフの、頂点数は高々 $2N$ 個、辺数はちょうど $N$ 本です。(つまりこのグラフの構築はTLに対して高速にできます)

以上のようなグラフを考えると、しりとりは以下のようなゲームに言い換えることができます。

高橋くんが最初 $S_{i}$ のSuffix3文字に対応する頂点を始点と決める。その状態から青木くん、高橋くん、青木くん、高橋くん....の順で有向グラフの辺を一本辿る。辺が存在しない(移動できない)場合はその人がゲームに敗北する。

これは基本的なゲームDPでできそうですが、今回は引き分け(グラフにサイクルがあって、そこを永遠にまわり続けるパターン)があります。

言い換えたゲームを観察する

引き分けがあり、いつものDPで機械的に処理できず(解いてる時の自分は)困りました。しかし、引き分けがある事以外はただのゲームDPであることに変わり無いので、DPで解くことを考えながらゲームの性質を観察しました。

DP[i] := 頂点iが始点だった時に高橋くんが勝つ(1)/負ける(0)/引き分け(-1)

明らかに出次数が $0$ の頂点 $v$ が始点だった場合、高橋君が勝ちます(始点が決められた後の青木くんのターンで移動できないので)
- dp[v] = 1
頂点 $v$ について、ある頂点 $x$ が存在してdp[x] = 1かつvからｘへの有向辺が存在する場合、頂点vを始点とすると青木くんが勝ちます
- 青木くんがxに移動することで「青木くんが始点を $x$ とした時の高橋->青木の順で同じゲームをする」ことになり、元のゲームのに対して勝敗がひっくり返るので
- dp[v] = 0
頂点 $v$ について、どのvから辺が伸びている頂点xについてもdp[x] = 0の場合、頂点 $v$ を始点とすると高橋君が勝ちます
- 2と同じように考える
- dp[v] = 1

ここまではトポロジカルソートの時と同様に辺を削除しながらよしなにやるとdpの値を確定させることができます。

上記以外の状況である頂点 $v$ を考えます - どの頂点 $v$ から辺が伸びている頂点xについて、dp[x] = 0またはdp[x] = ?で、かつdp[x] = ?となる頂点xが少なくとも一つ存在する場合

このような頂点が始点だった場合、まず青木くんはdp[x] = ?であるような頂点にしか移動できません
- dp[x] = 0である頂点に移動すると高橋君が勝つので
頂点xから辺が伸びている頂点yについて、dp[y]は0か?です。また、dp[y] = ?であるようなyが必ず存在します
- そうでない場合、dp[x]の値は確定しているので
高橋くんはdp[y] = ?であるような頂点yに移動します。
- dp[y] = 0であるような頂点に移動すると青木くんが勝つので

....

となり、dp[v] = ?であるような頂点を始点とした場合、永遠にゲームが続くことがわかりました。つまりdp[v] = -1です。

これですべての頂点についてdpの値が求まりました。ACですやったやった

この解析には名前がついている

ゲームを解く！Educational DP Contest K, L 問題の解説 - Qiita

後退解析と呼ぶようです。

頭の中の連想配列君にmp["DAGでないゲームDP"] = "後退解析" が登録されました。次からは脳死でやります。

提出コード

void main_() {
    i32 N; in(N);
    vector<string> S(N);
    for (auto& s : S) in(s);
 
    using str = array<char, 3>;
    map<str, vector<str>> G;
    map<str, i32> deg, dp;
 
 
    using str = array<char, 3>;
    for (const auto& s : S) {
        str pre{ s[0], s[1], s[2] }, suf{ s[s.size() - 3], s[s.size() - 2], s[s.size() - 1] };
        G[suf].push_back(pre);
        G[pre];
        deg[pre]++;
        deg[suf];
        dp[pre] = dp[suf] = -1;
    }
 
    queue<str> que;
    for (const auto& [s, d] : deg) if (d == 0) {
        dp[s] = 0;
        que.emplace(s);
    }
 
    while (que.size()) {
        auto v = que.front();
        que.pop();
        for (const auto& x : G[v]) if (dp[x] == -1) {
            if (dp[v] == 0) {
                dp[x] = 1;
                que.emplace(x);
            }
            else if (dp[v] == 1) {
                if (--deg[x] == 0) {
                    dp[x] = 0;
                    que.emplace(x);
                }
            }
            else {
                assert(!"bfs fail");
            }
        }
    }
 
    for (const auto& s : S) {
        str suf{ s[s.size() - 3], s[s.size() - 2], s[s.size() - 1] };
        if (dp[suf] == -1) {
            out("Draw");
        }
        else if (dp[suf] == 1) {
            out("Aoki");
        }
        else {
            out("Takahashi");
        }
    }
}

当時の自分は今回の説明とdpの値を逆にして解いていたようです。mapでグラフもっているせいで実行時間激遅でした。