2020年3月13日その他Grundy数,不偏ゲーム,組み合わせゲーム,スプレイグ・グランディの定理,Nim,NimK,テーマ記事,Misere Nim,競プロ,ゲーム

競技プログラミングなどで頻出のテーマである組み合わせゲームやGrundy数についてまとめました。

前半は全ての方に向けての内容で、プログラム例や競技プログラミング特有の話題については後半にあります。

組み合わせゲーム ...

2020年3月10日AtCoder二人零和有限確定完全情報ゲーム,後退解析,最大化,最小化,区間DP,DP,競プロ,ゲーム

問題へのリンク

問題概要

数列 \(a = a_1, a_2, \ldots, a_N \) がある。二人で以下の操作を交互に行う。

a の先頭要素または末尾要素を取り除く。 取り除いた要素を x& ...

2020年3月10日AtCoderDP,競プロ,ゲーム,二人零和有限確定完全情報ゲーム,後退解析

問題へのリンク

問題概要

二人で以下のゲームを行う。先手と後手のどちらが勝つか？

以下の操作を交互に行うA = \( a_1, a_2, \ldots, a_N\) の元 x を一つ選び、K 個の山から丁度 x 個取り ...