AtCoder Grand Contest 010: F - Tree Game
後輩が$700$点ぐらいだって言ってた。そう聞いてから解いたらそうだった。
solution
有向木にして始点ごとにDFS。$O(N^2)$。メモ化すれば$O(N)$だが不要。
頂点$i - j$が隣接していて$A_i \le A_j$だとしよう。 駒が$i$にあるときに$j$に動かすと、相手の番で$i$に戻されて$A_i-1 \le A_j-1$という状況になる。 これは繰り返せば自分が負ける。 つまり駒を石の数の減少する方向に動かせなければ負け。 逆に$A_i \gt A_j$であれば(相手が$i$に駒を戻すなら)これは勝ちとなる。
よって辺$i - j$を$A_i, A_j$の比較によって向きを付け、交互に動かして葉に辿り付いた方が負け。 これは$O(N)$のDFSで解ける。 始点については総当たりしても間に合う。
implementation
#include <cstdio>
#include <functional>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
int main() {
// input
int n; scanf("%d", &n);
vector<int> a(n); repeat (i, n) scanf("%d", &a[i]);
vector<vector<int> > g(n);
repeat (i, n - 1) {
int x, y; scanf("%d%d", &x, &y); -- x; -- y;
g[x].push_back(y);
g[y].push_back(x);
}
// solve
function<bool (int)> go = [&](int i) {
for (int j : g[i]) if (a[i] > a[j]) {
if (not go(j)) {
return true;
}
}
return false;
};
vector<int> result;
repeat (i, n) if (a[i]) {
if (go(i)) {
result.push_back(i);
}
}
// output
repeat (i, result.size()) {
printf("%d%c", result[i] + 1, i + 1 == result.size() ? '\n' : ' ');
}
return 0;
}