naoya_t@hatenablog

いわゆるチラシノウラであります

Codeforces Round #458 (Div. 1 + Div. 2)

agwたんリコメンドでCodecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined) より問題B

B: Conan and Agasa play a Card Game

http://codeforces.com/contest/914/problem/B

例えば 1,1,2,2,3,3 があるとする。
一番大きな数3が2つあるので2つ山を作る。
3未満の数は最初の山に全て載せる。
[11223] [3]

最初の山について、最大の3を除いた (1,1,2,2) について同様に、
一番大きな数2が2つあるので2つ山中山を作る。
2未満の数は最初の山中山に全て載せる。
{112} {2}

同様に
(1) (1)

プレイヤーは1手で山(あるいは山中山)をどれか1つだけ取れる。

こういう山がtreeになってるNimってよくあるよね?
→こんなやつ Game on Tree - AGC017:D
AGCだから解説つき

rootは2つの子ノード (11223, 3) を持ち、3の方はそこで終端、11223の方は2つの子ノード (112, 2) を持ち、2の方はそこで終端、112の方は2つの葉 (1, 1) を持つ。

子ノードが複数なら全ての子のXORを、1つならその子+1を、と集めていった値(Grundy数というやつだ)が非0なら先手の勝ち、0なら後手の勝ち。
→AC
http://codeforces.com/contest/914/submission/34532592