ABC 427 D 問題: DFSによる解法と計算量の考察

導入

AtCoder ABC 427 の D 問題につまずいたので、解いた過程と考察を残しました。
DFS で帰りがけ順に全探索する方針を立て、TLE したコードをメモ化再帰に直したことで AC できました。

問題

全文：ABC 427 D - The Simple Game

$T$ 個のケースが与えられますが、1 個の大きなケースについて十分高速に解ければ問題ありません。よって 1 ケースに限って解法を考えます。

問題は $N$ 頂点 $M$ 辺の有向グラフ上のコマの動きについて $2K$ 手先を読み切って勝敗を判断するという内容です。

初期方針

「互いに最善手を選ぶ」という部分がやや曖昧に感じましたが、「$K$ 手先を読み、各手番において自分が負けない手を選ぶ」と解釈し DFS で全探索する方針を取りました。
移動が終わったときに勝敗が確定するため、帰りがけ順に各状態での勝敗を定めていきます。

• 残り $t$ 回移動できるときコマが頂点 $u$ にある状態を $(t, u)$ とし、各状態における勝者を探索する
• 頂点 $u$ から辿れる全頂点 $v$ について $(t - 1, v)$ への遷移を考える
• すべての状態 $(t - 1, v)$ のうち手番を持つ側が勝つ遷移が存在すれば状態 $(t, u)$ はこちらの勝利、さもなくば相手側の勝利

実装

以下に AC した際のコードを示します。初回提出時 (TLE) のコードとの変更点は状態 $(t, u)$ のキャッシュの有無のみです。

def solve2(n, m, k, s, edges):
    # 隣接リスト (0-indexed) を作成する
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u - 1].append(v - 1)

    # 状態 (t, u) をキーとするキャッシュを用意する
    cache = dict()

    # 残り t 回移動し、コマが u にある場合の勝者を求める
    def dfs(t, u):
        # すでに探索済みの場合はキャッシュを返す
        if (t, u) in cache:
            return cache[(t, u)]

        # 移動が終わった場合 u の色 s[u] が勝者となる
        if t == 0:
            cache[(t, u)] = s[u]
            return s[u]

        # 残り移動回数が偶数の場合は A、奇数の場合は B の手番
        player = "A" if t % 2 == 0 else "B"
        enemy = "B" if player == "A" else "A"

        # player が勝てる手が一つでもあれば player の勝利、さもなくば enemy の勝利
        for v in graph[u]:
            if dfs(t - 1, v) == player:
                cache[(t, u)] = player
                return player
        else:
            cache[(t, u)] = enemy
            return enemy

    # 状態 (2k, 0) の勝者が求める解
    ans = dfs(2 * k, 0)
    return "Alice" if ans == "A" else "Bob"

メモ化を行うことで計算量を抑える

元のコードではメモ化を行っておらず、状態 $(t, u)$ の探索が重複していたために計算量が膨大になっていました。

メモ化を行わない場合の計算量

初めに提出したコードでは、同じ状態 $(t, u)$ を繰り返し評価することになります。
その結果出次数が多いグラフほど遷移数が増え、最悪のケースでは深さ $2K$、辺数 $N$ の木を探索することになり、最悪計算量は $\mathcal{O}(N^{2K})$ のような指数オーダーまで膨らみます。

メモ化を行った場合の計算量

これに対し、メモ化を行った場合の計算量を考えます。最終的に計算量は $\mathcal{O}(K(N + M))$ となります。

全体の計算量は「状態の数×各状態での辺の処理数」の合計で求められるため、状態の数および各状態での辺の処理の回数をそれぞれ考えます。

残り $t$ 回の移動で頂点 $u$ にコマがあるとき、勝者は一意に定まります。これは頂点 $u$ を初期位置、残り手数を $t$ 回としてゲームを開始したものと見なせることから説明できます。

状態 $(t, u)$ の総数は $t = 0...2K, u = 1...N$ より、たかだか

$$(2K + 1)N$$

個となります。

次に、各状態における辺の処理の回数（遷移の回数）を考えます。
$(t, u)$ から $(t - 1, v)$ への遷移は頂点 $u$ の出次数 $\mathrm{outdeg}(u)$と等しく、各 $t$ においてすべての $u$ の出次数の総和は $M$ と等しいため、全状態に対する辺の処理の総数は

$$\sum^{2k}_{t=1} \sum_{u} \mathrm{outdeg}(u) = 2KM$$

と求められます。状態の管理と辺の処理を合わせて、最終的な時間計算量は

$$\mathcal{O}((2K + 1)N + 2KM) = \mathcal{O}(K(N + M))$$

となり、与えられた制約で十分高速です。

公式解説との違い

公式解説では DP テーブルを使った解法が紹介されていますが、状態の定義と遷移が等しいことからメモ化を行った DFS と本質的な違いはなく、どちらも同じアルゴリズムを使った解法であると言えます。

まとめ

DFS でメモ化のことを忘れてしまいがちですが、同じ状態は一度だけ評価すれば十分ですね。
同様にこの問題や類題で苦戦した人の参考になれば幸いです。