けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

KUPC 2019 E - 根付き森二人用ゲーム

AtCoder KUPC 木 DP 木DP パリティ 場合分け ゲーム ゲームDP 木上のゲーム 駒(コマ)や石やコインを扱う問題 グラフ上のゲーム

200 点となってるけど、他の 300 点と同じくらいに感じた！
頭の整理が大変だった...けど、面白い

問題へのリンク

問題概要

N 個の根付き木が与えられる。それぞれの木の頂点数は M_1, M_2, \dots, M_N となっている。これらの木を使って、ゲームを行う。

  • 最初、駒がスタート地点 (どの木にも属さない) に置かれている
  • 駒がスタート地点にある状態で手番の人は、まだ一度も使っていない木を一つ選んで、その木の根に駒を動かす
    • すべての木が使用済みであった場合は、手番の人が負けである
  • 駒が木上にある状態で手番の人は
    • 駒が木の葉上にある場合は、スタート地点へと移動させる
    • 駒が木の葉以外の頂点上にある場合は、その子頂点のうちの一つを選んで、その子頂点へと移動させる

双方が最善を尽くしたとき、先手と後手のどちらが勝つか？

制約

  • 1 \le N \le 10^{5}
  • \sum_{i} M_{i} \le 2 \times 10^{5}

考えたこと

こういうの、まずは木が 1 個の場合を考えるのよいと思う！！！！！

  • 1 頂点だけだったら、先手が根にやって、後手がスタートに戻して、先手は手詰まりなので後手勝ち
  • 深さ 2 で 2 頂点だけだったら、先手が根にやって、後手が葉にやって、先手がスタートに戻して、先手勝ち
  • 一般に、すべての葉の根からの深さが等しかったら、その偶奇によって、先手必勝か後手必勝かが変わる

もう少し一般化すると、

  • 一つの木に対して、先手必勝か後手必勝かは木 DP で求められる
    • 葉はスタートに戻せるので勝ちノード
    • そこから上はよくある AND / OR 探索で OK

木が複数あるとき

木を選ぶ順序もいじれるのでちょっと複雑。一つ観察として木は

[0] 2 人がどう頑張っても手番がそのまま (最後に後手が葉からスタートに移す)
[1] 2 人がどう頑張っても手番が入れ替わる (最後に先手が葉からスタートに移す)
[2] 手番を握った人が、最後の手番をどちらにするかを制御できる
[3] 手番を握った人と反対側の人が、最後の手番をどちらにするかを制御できる

の 4 通りがあることがわかる。そして

  • パターン 2 が 1 個でもあったら、先手が勝てる
    • 「その 1 個のパターン 2」を取り除いた盤面は「先手必勝」か「後手必勝」かどちらかなのだ
    • それが先手必勝なら、後手にスタートに戻らせればよい
    • それが後手必勝なら、先手がスタートに戻るようにすればよい

ということがわかるので、パターン 2 はないものとして考えよう。先手目線だと

  • もう残りの木がない
  • もう残りの木がパターン 3 しかない

というのはまったく同じ状態として考えることができる。よって、パターン 3 もないものとしてよい。さらに、パターン 0 も影響ないことがわかる。

最終的に、パターン 1 のみが問題になる。パターン 1 が偶数個だったら先手負け、奇数個だったら後手負け。

パターンを求める

最後にパターンを求める。普通のゲーム木に対するゲーム DP と大体一緒。

  • 葉はパターン 1
  • 頂点 v がパターン 0 とは、パターン 3 の子頂点はなく、パターン 2 以外の子頂点がすべてパターン 1 である場合
  • 頂点 v がパターン 1 とは、パターン 3 の子頂点はなく、パターン 2 以外の子頂点が子頂点がすべてパターン 0 である場合
  • 頂点 v がパターン 2 とは、子頂点中にパターン 3 が存在するか、パターン 0 とパターン 1 のいずれもが存在する場合
  • 頂点 v がパターン 3 とは、子頂点がすべてパターン 2 である場合

注意点として、スタートは「根」ではなく、「スタート地点」なので、根の親として仮想的なスタート地点を設けて、そのスタート地点のパターンを求めることとした。

#include <iostream>
#include <vector>
using namespace std;

using Graph = vector<vector<int> >;

// 0: 手順は絶対変化なし
// 1: 手順は絶対変化あり
// 2: 先手が好きな手番に変化できる
// 3: 後手が好きな手番に変化できる
int rec(const Graph &G, int v = 0) {
    if (G[v].empty()) return 1;
    
    bool ex0 = false, ex1 = false;
    for (auto ch : G[v]) {
        int chtype = rec(G, ch);
        if (chtype == 0) ex0 = true;
        else if (chtype == 1) ex1 = true;
        else if (chtype == 3) return 2;
    }
    if (!ex0 && ex1) return 0;
    else if (ex0 && !ex1) return 1;
    else if (ex0 && ex1) return 2;
    else return 3;
}

bool solve() {
    int N; cin >> N;
    int num_pat1 = 0;
    while (N--) {
        int M; cin >> M;
        Graph G(M+1);
        G[0].push_back(1);
        for (int i = 0; i < M-1; ++i) {
            int p; cin >> p;
            G[p].push_back(i+2);
        }
        int type = rec(G);
        if (type == 2) return true;
        if (type == 1) ++num_pat1;    
    }
    if (num_pat1 % 2 == 1) return true;
    else return false;
}

int main() {
    if (solve()) cout << "Alice" << endl;
    else cout << "Bob" << endl;
}