C++で解くマス塗り分けゲームの勝者判定プログラム

問題の概要

要素数Nの2つの配列AとBがあるとします。Amal（アマル）とBimal（ビマル）の2人が、1からNまでの番号が振られたマスを持つ盤面でゲームを行います。盤面にはN-1本の道があり、i番目の道はマスA[i]とマスB[i]を結んでいます。どのマスからでも、隣接するマスへの移動を繰り返すことで他のすべてのマスに到達できます。つまり、この盤面は木構造になっています。

初期状態では、マス1が黒色、マスNが白色に塗られており、それ以外のマスは無色です。Amalが先手となり、2人は交互に手番を進めます。Amalは黒いマスに隣接する無色のマスを選んで黒く塗り、Bimalは白いマスに隣接する無色のマスを選んで白く塗ります。そして、塗れるマスがなくなったプレイヤーの負けとなります。このゲームの勝者を求めるのが目的です。

例えば、入力が A = [3, 1, 3, 7, 5, 1]、B = [6, 2, 1, 4, 7, 4] の場合、出力は「Amal」になります。Amalが最初にマス2を黒く塗れば、Bimalがどんな手を指しても勝利できるからです。

解法のステップ

この問題を解くために、以下の手順に従います。

N := 99999
隣接リスト adjList を定義
3つの大きな配列 p、d、ssz を定義
関数 dfs() を定義（引数： nd、par、dep）
    p[nd] := par
    d[nd] := dep
    ssz[nd] := 1
    adjList[nd] 内の各ノード i について：
        i XOR par が 0 以外の場合：
            dfs(i, nd, dep + 1) を呼び出す
            ssz[nd] := ssz[nd] + ssz[i]
mainメソッドでは以下を実行：
n := A のサイズ
i := 1 から i < n の間、i を1ずつ増やしながら繰り返す：
    u := A[i - 1]、v := B[i - 1]
    adjList[u] の末尾に v を追加
    adjList[v] の末尾に u を追加
dfs(1, 1, 0) を呼び出す
nd := n
i := 0 から i < (d[n] - 1) / 2 の間、i を1ずつ増やしながら繰り返す：
    nd := p[nd]
2 * ssz[nd] >= n なら "Bimal" を返し、そうでなければ "Amal" を返す

アルゴリズムのポイント

このアルゴリズムの鍵は、マス1からマスNまでの経路の中間地点付近にあるマスを特定し、そのマスを根とする部分木のサイズを評価することです。中間マスの部分木サイズが盤面全体の半分以上であればBimalが有利、半分未満であればAmalが有利であると判定できます。DFS（深さ優先探索）を使うことで、各ノードの親・深さ・部分木サイズを効率よく一度に計算できるのが特徴です。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int N = 99999;

vector<vector<int>> adjList(N);
vector<int> p(N), d(N), ssz(N);

void dfs(int nd, int par, int dep){
    p[nd] = par;
    d[nd] = dep;
    ssz[nd] = 1;
    for (int i : adjList[nd]){
        if (i ^ par){
            dfs(i, nd, dep + 1);
            ssz[nd] += ssz[i];
        }
    }
}
string solve(vector<int> A, vector<int> B){
    int n = A.size();
    for (int i = 1; i < n; i++){
        int u = A[i - 1], v = B[i - 1];
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    dfs(1, 1, 0);
    int nd = n;
    for (int i = 0; i < (d[n] - 1) / 2; i++)
        nd = p[nd];
    return (2 * ssz[nd] >= n ? "Bimal" : "Amal");
}
int main(){
    vector<int> A = { 3, 1, 3, 7, 5, 1 };
    vector<int> B = { 6, 2, 1, 4, 7, 4 };
    cout << solve(A, B) << endl;
}

入力

{ 3, 1, 3, 7, 5, 1 }, { 6, 2, 1, 4, 7, 4 }

出力

Amal