https://kenkoooo.com/atcoder/#/contest/show/28c6016e-1df1-4039-aeee-95f2777bd5ac
■01.
D - Harlequin(CADDi 2018 for Beginners)
https://atcoder.jp/contests/caddi2018b/tasks/caddi2018_b
・取りうる状態を考える
状態A：すべてのりんごが偶数個
状態B：どれか１つのりんごが奇数個
終了状態はA(all0)
状態の変化はA->B,B->{A,B}
Aの状態を相手に渡せば真似っ子戦略を行い
常にAの状態で相手に手番を渡せる。
よってどれか１つでも奇数なら先手の勝ち
■02.
D - Two Piles(CPSCO2019 Session2)
https://atcoder.jp/contests/cpsco2019-s2/tasks/cpsco2019_s2_d
・極端な例を考える
(x,1)の状態からの行動を考える
(x,1)->(x,0),(x-1,1),(1,0),(0,1)
(0,n)にすると次に全取りされて負けるので
(x-1,1)に遷移させたいが、同じことの繰り返しなので
(2n,1)なら手番が勝つ
(2n+1,1)なら手番が負ける
(n,m)から(x,1)への遷移を考える
(2n,2m)->(奇数,1)は可能：手番勝ち
(2n+1,2m)->(奇数,1)は可能：手番勝ち
(2n,2m+1)->(奇数,1)は可能：手番勝ち
(2n+1,2m+1)->(奇数、偶数)にしかならない、手番負け
■03.
B - 石取り大作戦(AtCoder Regular Contest 046)
https://atcoder.jp/contests/arc046/tasks/arc046_b
・大小関係で場合分け
まずn<=aなら初手で全取りして先手が勝つ(コーナーケース)
a=bのときは有名なゲームになる
0==n%(a+1)なら後手勝ち、そうでないなら先手勝ち
a≠bなら？
a
1,x,1,y,1,z,1としておけばいい
■04.
C - Zero XOR(AtCoder Regular Contest 131)
https://atcoder.jp/contests/arc131/tasks/arc131_c
・偶奇で場合分け
残りが偶数個の場合：初手で残りのxorが0に出来るなら勝ち
そうでないなら残りが奇数個の場合移る。
残りが奇数個の場合：
２ターン後に終了する条件は？
先手が何をしても適切なものを選んでxorを0にする事ができる。
だが、これは残りが重複の無い奇数個な集合なため不可能。
なので"先手が勝つ" or "n-2"個になってゲームが続行する
なので先手必勝になる
■05.
H - 8^kゲーム(全国統一プログラミング王決定戦 エキシビジョン)
https://atcoder.jp/contests/nikkei2019-ex/tasks/nikkei2019ex_h
・簡単な問題に帰着させる
8^n=(-1)^n (mod9)
で考えてmod9で値は２ターンごとに不変にできる。
■06.
A - Div/de(DISCO presents ディスカバリーチャンネル コードコンテスト2020 本戦)
https://atcoder.jp/contests/ddcc2020-final/tasks/ddcc2020_final_a
・grundy数
grundy数を求める
■07.
A - Taro vs. Jiro(第5回 ドワンゴからの挑戦状 本選（オープンコンテスト）)
https://atcoder.jp/contests/dwacon5th-final-open/tasks/dwacon5th_final_a
・kが小さい場合に帰着する
k=2n+1のとき
k=1で先手が勝つなら3,5,7,9...手目は2,4,6,8...手目の後手の操作の逆をすればいい
k=1で後手が勝つなら2,4,6,8...手目は1,3,5,7...手目の先手の操作の逆をすればいい
k=2nも同様
なのでk=1,2をdpすればいい
■08.
D - An Ordinary Game(AtCoder Beginner Contest 048)
https://atcoder.jp/contests/abc048/tasks/arc064_b
・最終状態をイメージする
ababababのような状態になり最初と最後はsと同じ。
なので操作が行われた回数の遇奇がわかる
■09.
D - Alice&Brown(AtCoder Beginner Contest 059)
https://atcoder.jp/contests/abc059/tasks/arc072_b
・実験をする
(i,j)から始めるとしてi+jは単調に減少するのでdpテーブルが埋まる
■10.
C - 笑いをとれるかな？(AtCoder Regular Contest 013)
https://atcoder.jp/contests/arc013/tasks/arc013_3
・nimに帰着
ただのnim
■11.
D - Let's Play Nim(AtCoder Regular Contest 105)
https://atcoder.jp/contests/arc105/tasks/arc105_d
・Nim亜種
袋への操作がすべて終わった段階で全体のxorを0にして相手に手番を渡す必要がある。
Nが奇数のとき
後手は特定の皿に過半数の要素を載せることができる。するとxorは0にならない
Nが偶数のとき
逆にすることで先手が過半数の要素を載せることができる
が、全部ペアだと無理
■12.
C - Piles of Pebbles(C - Piles of Pebbles)
https://atcoder.jp/contests/arc143/tasks/arc143_c
・大小関係で場合分け
ai%=(x+y)してよい
x<=y
∀i ai < xなら後手が勝つ(後手は先手の真似っ子すればいい)
∃i ai>=xなら先手勝ち(初手でそれにのみ操作すればai
∀i ai < xなら後手が勝つ(後手は先手の真似っ子すればいい)
∃i y<=ai < xなら後手勝ち
それ以外先手勝ち
■13.
C - Removing Coins(AtCoder Grand Contest 033)
https://atcoder.jp/contests/agc033/tasks/agc033_c
・直径に着目する
操作によって直径が１or2減る
1,2は自由に選択できるなので有名なゲームに帰着される
■14.
C - Distinct Numbers(AtCoder Regular Contest 137)
https://atcoder.jp/contests/arc137/tasks/arc137_c
・２手先まで考える
a[n-2]+2<=a[n-1]なら
1:a[n-1]をa[n-2]より小さい要素に変更する
か
2:a[n-1]+1に変更する
1の遷移先に手番が必敗局面があるなら先手勝ち
ない(全ての遷移先が手番が必勝)なら、2を行う
すると後手が先手に手番が必勝な局面を渡すことになるので先手勝ち
a[n-2]+1=a[n-1]のとき
上の考えより最大と次に大きいものの差が1の状態を保ち続けたい
なのでmax(A)は毎ターン１減っていき最終状態が(n-1,n-2,n-3,,,,,,0)となる
■15.
D - mod M Game(AtCoder Regular Contest 148)
https://atcoder.jp/contests/arc148/tasks/arc148_d
以下全てmod m
Sa=Sbになれば後手の勝ち
Sa+Sa=Sa+Sb
2Sa=S
先手はこれを避ける立ち回りをする必要がある
後ろから考える
最終ターンに先手の選択肢が二つあれば(x,y)先手勝ち
もう一つ前を考える
(x,x,y,z)とかならxを取ればいいので先手勝ち
(x,x,y,y)なら後手真似っ子戦略をするのが最善
奇数個が２つ以上あれば先手勝ちを示したい
奇数が３つ以上にして渡せるなら先手勝ち
奇数が２偶数が０のときは？
先手がが初手を選んであとは後手の真似っ子をすればいい
すべてが偶数個のとき
後手は真似っ子が最善なのでその時に後手が勝てるかをしらべる
■16.
C - Parity(技術室奥プログラミングコンテスト#4 Day2)
https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_c
・実験
実験コードを書いてにらみつけると周期がわかる
周期がわかれば証明もできる
■17.
J - Color Game(CODE FESTIVAL 2014チーム対抗早解きリレー)
https://atcoder.jp/contests/code-festival-2014-relay/tasks/code_festival_relay_j
・ペアを考える
そもそもkが一定以上なら初手に真ん中を選んだらゲームが終わる
kが一定以下の場合を考える
偶数のとき
(1,n/2)(2,n/2+2)とペアを作り
選ばれた者の相方を後手は選べばいいので後手が勝つ
奇数のとき
初手で中心を選ぶと偶数のときと同じ戦略をすればいいので先手勝ち
■18.
G - 石取りゲーム(code thanks festival 2014 B日程（オープンコンテスト）)
https://atcoder.jp/contests/code-thanks-festival-2014-b-open/tasks/code_thanks_festival_14_qualb_g
状態、遷移が少ないので再帰が回る
■19.
J - 石山ゲーム(CODE FESTIVAL2015チーム対抗早解きリレー)
https://atcoder.jp/contests/code-festival-2015-relay/tasks/cf_2015_relay_j
実験をするACが証明
■20.
F - お祭りとお菓子(CODE THANKS FESTIVAL 2015 オープンコンテスト)
https://atcoder.jp/contests/code-thanks-festival-2015-open/tasks/code_thanks_festival_2015_f
初手で勝てるなら先手勝ち
あとは部分木を減らしていくしか無いのでmod2
■21.
F - ピラミッド - 誕生日編 (Golden Week Contest 2015)
https://atcoder.jp/contests/gwcontest2015/tasks/gw2015_f
メモ化再帰をするには状態数が多すぎますね。
状態を減らすために適切な考察をすると
各要素全てを保持する必要はなく
最小値と合計を持っていればいいことがわかる。
■22.
F - カード集め(Kyoto University Programming Contest 2018)
https://atcoder.jp/contests/kupc2018/tasks/kupc2018_f
・"両方〇〇したらx点"⇔"片方〇〇するごとにx/2点"
天才言い換え典型？
■23.
D - Stones(京都大学プログラミングコンテスト 2021)
https://atcoder.jp/contests/kupc2021/tasks/kupc2021_d
・grundy数
実験すると見える
■24.
D - Black and White Tree(AtCoder Grand Contest 014)
https://atcoder.jp/contests/agc014/tasks/agc014_d
完全マッチングが存在するかどうか
■25.
D - Game on Tree(AtCoder Grand Contest 017)
https://atcoder.jp/contests/agc017/tasks/agc017_d
・grundy数
完全マッチングが存在するかどうか
■
こっからは無理だ
