Atcoder AGC 010 F. Tree Game

F: Tree Game - AtCoder Grand Contest 010 | AtCoder

この点数の問題を完全に自力で通せたので驚いた。こういうタイプの問題が得意になってきた（気がする）ので嬉しい。思考の流れもまとめて記述しておく。まぁ順位表見てもわかるように、さすがに1600点の難易度ではない。

解法

まず、自分が移動させた結果、$\ a = 0\ $であるような頂点に移動した場合、勝ちである。また「周囲の頂点がすべて$\ a > 1\ $であり、かつ$\ a = 1\ $であるような頂点」に移動した場合も、同様に勝ちである。なぜなら、次の自分の番にまたその頂点に戻ってくることが可能だからである。

より一般的に、「周囲の頂点がすべて$\ a > k\ $であり、かつ$\ a = k\ $であるような頂点」に移動した場合も勝ちである。上と同様に、それ以降常に相手の動きの逆の動きをとればよい。

ここまでの考察で、今いる頂点$\ v\ $から移動するべき頂点$\ u\ $は、$\ a_v > a_u\ $を満たすような頂点のみであることが推測でき、それは実際正しい。なぜなら、仮に$\ a_v \leq a_u\ $となる頂点に移動することで自分が有利になるのだとしたら、相手はその方向に行かせないようにするはずなので、$\ a_u\ $から$\ a_v\ $に戻るような手を打つはずである。このとき、両方の$\ a\ $の値が$\ 1\ $ずつ減少するが、大小関係は変わらないので、これを繰り返しても負けることになるだけである。よってこのような移動はする意味がない。

以上の考察で、常に$\ a\ $が小さくなるような遷移を繰り返していくことで、決着がつくことが示された。実装を簡単にするために、そもそも$\ a_v < a_u\ $を満たすようなところにのみ$\ a_u\ $から$\ a_v\ $に向かって有向辺を張っておけばよい。これでそのまま遷移先をすべて考えることができる。

勝敗の判定は普通にやればよい。すなわち、まず行き先がそれ以上ない場合は、$\ lose\ $の状態である。行き先がある場合は、その行き先のいずれかに$\ lose\ $の状態があるならばそこに移動すればよいので$\ win\ $、すべて$\ win\ $となってるときはどう動いても負けるので$\ lose\ $とすればよい。

$\ O(n)\ $。なぜ$\ 2 \leq n \leq 3000\ $なのかがいまいちわからない。

実装

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

vector<int> a;
vector<vector<int>> g;
vector<bool> win;
vector<bool> used;

bool dfs(int v) {
        used[v] = true;
        if (g[v].size() == 0) return win[v] = false;
        bool lose = true;
        for (int u : g[v]) lose &= dfs(u);
        return win[v] = !lose;
}

int main() {
        int n;
        cin >> n;
        a.resize(n);
        g.resize(n);
        win.resize(n);
        used.resize(n, false);
        for (int i = 0; i < n; i ++) cin >> a[i];
        for (int i = 0; i < n - 1; i ++) {
                int u, v;
                cin >> u >> v;
                u --, v --;
                if (a[u] == a[v]) continue;
                if (a[u] > a[v]) g[u].push_back(v);
                else g[v].push_back(u);
        }
        for (int i = 0; i < n; i ++) if (!used[i]) dfs(i);
        for (int i = 0; i < n; i ++) if (win[i]) cout << i + 1 << ' ';
        return 0;
}