競プロ日記

新年初(記事にする)問題。


コード
https://atcoder.jp/contests/caddi2018b/submissions/3928826


解説見たらだいぶ簡単だけど思いつけない。
問題読んでまずゲーム木の問題なんだろうなぁと考えたけどゲーム木っていう言葉くらいしか知らないからどうしようかと。
結局諦めて解説見たわけだけどたぶん数時間考えても解けてなかったと思う。

今回の学びは、2人が順番に何か操作する問題を解くのコツは自分が完全にコントロールできる部分を把握するべし、ということ。
「1～3までの数字を順番に言って最後に10言ったら勝ちゲーム」でも、自分と相手が言う合計は最小で4にコントロールできることから、4の倍数を考えることが勝つためのコツとなる。
今回の問題だと、「各種1つずつまでしか取れない→各種の2の倍数を考える」と考えればよかったのだろう。

これが3人になるとどうすれば良いのだろうか。
取る数が0か1だとすると、2人の取り方で0～2の範囲がある時点で自分が取れる0,1では全くコントロールできない。
0と3は能動的に避けることができるが、1か2に絞るのが精一杯だろう。
そういう問題が出たらどう解けばいいんだろうか？
再帰で解ける範囲なら解けそうだが、それ以上になると無理だろう。
また別の考え方があるのだろうか。