AtCoder ABC 246 G - Game on Tree 3 (黄色, 600 点)

めっちゃ面白い問題だった！

• 問題へのリンク

問題概要

頂点 0 を根とする頂点数 の根付き木が与えられます。頂点 0 以外の頂点 には数値 が書かれています。今、頂点 0 にコマが置いてあります。

高橋くんと青木くんが次の動作を交互に繰り返します。

• 青木くんは、好きな頂点を選んで、その頂点の値を 0 にする
• 高橋くんは、コマを子頂点のいずれかに移動させる。移動できないときはその場でゲームを終了する

高橋くんは任意のタイミングでゲームを終了できます。そしてゲーム終了した時のコマの置かれた頂点の数値が、ゲームのスコアとなります。

高橋くんはスコアの最大化を目指し、青木くんはスコアの最小化を目指します。双方が最善を尽くしたときのゲームのスコアを求めてください。

制約

• 

考えたこと

まず真っ先に二分探索したいと思った。そうすれば、白黒ゲームになる。つまり、各頂点が白または黒に塗られていて、

• 高橋くんは黒頂点に着地することを目指す
• 青木くんは黒頂点を白く塗りつぶすことで、高橋くんが黒頂点に着地するのを阻止することを目指す

というゲームになる。このように、二分探索することで、ゲームだったりグラフだったり盤面だったりを白黒にするケースはよくある気がする。

白黒ゲームの解き方

まず思ったのは、高橋くんが勝てる場合、勝つ直前は下図のように「コマのある頂点の子頂点のうち、2 個以上が黒色」という状況にある。

1 個だけが黒色だと、先に青木くんに白色にされて勝てない。でも 2 個が黒色なら青木くんが両方を白色にする前に高橋くんが黒色頂点に着地できるのだ。

そしてさらに言えば、3 個が黒色なら、コマがもう一歩手前にあっても間に合う。

この状況を一般化して、各頂点の「余裕値」を求められそうだ。つまり次のような値を計算できそうだ。

---

dp[v] ← 頂点 にコマがある状態から、青木くんに何手先に操作されても、高橋くんが黒頂点に着地できるか

---

たとえば、

• 黒頂点自体の余裕値は 1 (すでに着地していることから)
• 子頂点のうちの 2 個が黒頂点であるような頂点の余裕値は 1
• 子頂点のうちの 3 個が黒頂点であるような頂点の余裕値は 2

となる。もっと一般に、次のような木 DP で余裕値が求められる。

dp[v] = dp[c] + (頂点 が黒頂点 ? 1 : 0)

そして dp[0] が 1 以上なら高橋くんの勝ち、0 なら青木くんの勝ち。この DP に要する計算量は となる。

よって二分探索法全体を合わせると、全体の計算量は として、 と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

int main() {
    int N;
    cin >> N;
    vector<int> A(N, 0);
    for (int i = 1; i < N; ++i) cin >> A[i];
    Graph G(N);
    for (int i = 0; i < N-1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    long long low = -1, high = 1LL<<60;
    while (high - low > 1) {
        long long x = (low + high) / 2;

        auto dfs = [&](auto self, int v, int p = -1) -> int {
            int res = 0;
            for (auto ch : G[v]) {
                if (ch == p) continue;
                res += self(self, ch, v);
            }
            return max(0, res - 1) + (A[v] >= x);
        };

        if (dfs(dfs, 0) >= 1) low = x;
        else high = x;
    }
    cout << low << endl;
}

別解

二分探索ではない方法で で求められる方法がある。さっきの DP で言えば、

dp[v][x] ← 数値が 以上である頂点を黒頂点であるとした場合の、頂点 の余裕値

とする。配列 dp[v] の値は、 に応じて単調減少となるが、変化する部分は高々 箇所しかないのだ。

よって dp[v] の値は、変化点も含めて、高々 次元ベクトルで管理できる。

木 DP を組むときに、マージテクを使い、さらにヒープのマージを高速にできる meldable heap を用いることで の計算量となる。

詳細は Nachia さんのユーザ解説にて

atcoder.jp