ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

グランディ数

AGC010 D - Decrementing

問題 提出コード 解法 わかりやすい部分、つまりが小さい方から考えていきます。 のとき 1回の操作で必ず1減少するので、明らかに、の偶奇で答えが判定できます。 奇数であれば後手勝ち、偶数であれば先手勝ちです。 のとき のどちらかが1であった場合、先ほ…

京都大学プログラミングコンテスト 2020 H - Beans on the Grid

問題 提出コード 解法 豆は自由に選んで操作できるので、定石通り、それぞれの豆に対してグランディ数を求め、最後にxorを取れば良いです。 まず、とりうるグランディ数の値を考えると、遷移先としてあり得るのが{右、左、下}の3パターンが最大です。よって…

AOJ 3057 - First Kiss (RUPC2019 Day2 G)

問題 提出コード 解法 まずは、キッポーが1本のときについて考えます。 この問題についてのグランディ数を求めることができれば、あとは本のキッポーについてのグランディ数のxorを取った結果を見ればよいです。 キッポーの長さを0にした方が負けなので、1だ…

Educational DP Contest / DP まとめコンテスト K - Stones

問題 提出コード 解法 素直にグランディ数を求めれば良いです。例によってグランディ数についてはこちらがわかりやすいかと思います。 グランディ数 - zukky162のブログ 今回は、重要なのがグランディ数は0であるか1であるか、なので2以上の場合も1にしてし…

グランディ数の問題の解き方メモ (ARC072 D - Alice&Brown)

あまりに苦手なので、やまさん(@yamasangamasan)に解き方のコツを聞いたのでメモしました。文章だらけなのでかなり読みづらいです... グランディ数を使う問題は、 二人零和有限確定完全情報ゲームです(!) AとBの2人がいて、ある操作行うようなゲームをしま…

ABC048 D - An Ordinary Game

問題 提出コード グランディ数を利用する問題は、ぱっとみで使うだろうなーというのがわかっても、そこから答えに結び付けるのが難しくていつも解くのに時間がかかります… 解法 お互いが操作できなくなる状態では、必ず2種類の文字になっていて、それが交互…

ARC087 E - Prefix-free Game

問題 提出コード 解法 グランディ数の問題かつ、二分木が関係していて…と割と惜しいとこまではいけた(つもり)なのですが、最後がうまくまとまらなかったので解説を見てACしました。 完全二分木を組み立て、そこに今回の文字列をうまく落とし込むと、現在選…

AOJ 1518 - Last One

Last One | Aizu Online Judge 提出コード グランディ数についての問題を初めて解きました。 数週間前にこちらのブログを読んでいたので、知識としてはなんとなくありました。 zukky162.hatenablog.com この記事に書いてあることさえわかれば、この問題はな…