東京工業大学プログラミングコンテスト2015 M - コインと無向グラフ
問題
頂点数n、辺数mの無向グラフが与えられ、グラフの各頂点iにはコインがc[i]枚乗っている
各プレイヤーは交互に以下の操作を繰り返す
1) 頂点0以外で頂点0と連結な頂点を1つ選び、それをjとする
2) jに隣接する頂点のうち、jより頂点0に近い点を1つ選び、それをkとする
3) jからkにコインを1枚以上移動する
先にコインを移動できなくなった方が負け
両者が最善を尽くすときどちらが勝つか
1 <= n <= 10^5
1 <= m <= 2*10^5
0 <= c[i] <= 10^8
解法
とりあえず頂点0からBFSして、各頂点への最短距離を求める
(ちなみにここで使わなかった辺は必要なくて、この辺を消すと頂点0を根とした根付き木になる)
するとこのゲームは、頂点0からの最短距離が奇数であるような頂点を山、それらに乗っているコインの数を石としたnimと見なすことができる
(距離が偶数の山に操作をしても返しのターンで元の状態に戻せるため)
xor和が0でなければ先手の勝ち、0なら後手の勝ち
int n, m, a[100100], d[100100], x, y, xo; vector<int> e[100100]; signed main() { cin >> n >> m; rep(i,n) cin >> a[i]; rep(i,m) { cin >> x >> y; e[x].push_back(y), e[y].push_back(x); } reps(i,1,n) d[i] = inf; queue<int> q; q.push(0); while (!q.empty()) { int v = q.front(); q.pop(); each(i,e[v]) if (d[i]>d[v]+1) q.push(i), d[i] = d[v]+1; } rep(i,n) if (d[i]%2) xo ^= a[i]; cout << (xo ? "First" : "Second") << endl; }