ABC246 G - Game on Tree 3 - koba-e964の日記

かなり手間取った。
G - Game on Tree 3

問題

頂点 1 を根とした N 頂点の根付き木があり、頂点 1 以外には正の整数が書かれている。木の頂点 1 に駒を置き、高橋君と青木君は以下のようなターン制のゲームを行う。
1. 青木君は頂点 1 以外の頂点を選び、書かれている整数を 0 にする
2. 高橋君は駒の置かれている頂点の子のどれか一つに駒を動かす
3. 駒の置かれている頂点が葉であればゲーム終了。そうでなくても高橋君は自分の判断でゲームを終了できる。

ゲーム終了時に駒の置かれている頂点に書かれている整数が得点である。高橋君の目標は得点の最大化、青木君の目標は得点の最小化である。
両者が最適にプレイする時の得点を求めよ。

解法

二分探索により、各頂点に 0 か 1 が書いてあり、高橋君は 1 に到達できれば勝ち、青木君は阻止できれば勝ち、というゲームになる。

各頂点に対し評価値を、その頂点を根とした部分木で青木君が勝つために必要な手数 (1 を 0 にする回数) とする。各ターン、青木君には子孫のうちどれかを 0 にするという 1 手の余裕があり、高橋君は評価値最大の子を選べばよいので、子の評価値の和が 2 以上であれば勝つことができ、またそれより大きければそれだけ青木君が必要な手数も増える。また、頂点に書かれている数が 1 であれば即座に高橋君が勝つので、青木君はこれも 0 にしなければならない。よって評価値 = max(子の評価値の和 - 1, 0) + 自分に書かれている値である。

登場する典型

二分探索
木 DP
二人有限確定完全情報ゲーム

実装上の注意点

特になし

提出:
#30672562 (Rust)

// Does Takahashi win?
fn dfs(v: usize, par: usize, g: &[Vec<usize>], b: &[bool]) -> i32 {
    let mut num = 0;
    if b[v] {
        num += 1;
    }
    let mut ma = 0;
    for &w in &g[v] {
        if w == par { continue; }
        let sub = dfs(w, v, g, b);
        num += sub;
        ma = max(ma, sub);
    }
    if ma > 0 {
        num -= 1;
    }
    num
}
 
fn solve() {
    input! {
        n: usize,
        a: [i64; n - 1],
        uv: [(usize1, usize1); n - 1],
    }
    let mut a = a;
    a.insert(0, 0);
    let mut g = vec![vec![]; n];
    for &(u, v) in &uv {
        g[u].push(v);
        g[v].push(u);
    }
    let mut pass = 0;
    let mut fail = 1 << 30;
    while fail - pass > 1 {
        let mid = (fail + pass) / 2;
        let b: Vec<bool> = a.iter().map(|&a| a >= mid).collect();
        let ans = dfs(0, n, &g, &b);
        if ans > 0 {
            pass = mid;
        } else {
            fail = mid;
        }
    }
    println!("{}", pass);
}

まとめ

適切な評価値を思いつくのが難しく、[i64; 2] (部分木に対して、そこで 0 にする操作をするかどうかで場合分け) などでうまくいくかどうかを無駄に考えてしまっていた。