Nim
コンテスト中にアダマール変換を思い出せたのはよかった! 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…
Grundy 数は Grundy 数でも、「山を分割していく」というタイプの Grundy 数ですね。 問題へのリンク 問題概要 個の区間が与えられる。 個目の区間は となっている。 Alice と Bob は次のようなゲームを行う。 まだ残っている区間のうち、「今までに選ばれた…
面白かった! 問題へのリンク 問題概要 個の石の山がある ( は偶数)。 番目の山には 個の石がある。先手と後手が交互に以下の操作を行う。操作できなくなった方が負けである 石の山のうち、まだ石が 1 個以上残っている山をちょうど 子選ぶ そのそれぞれの山…
Grundy 数がフラクタルっぽい構造を示していた! 問題へのリンク 問題概要 個の石の山がある。各山には 個の石がある。先手と後手が交互に以下の操作を繰り返す。 山を一つ選ぶ。その山には石が 個あるとする。 その山の石の個数が 個または 個となるように…
これ結構好き! 問題へのリンク 問題概要 それぞれ 枚のコインの入った 枚の袋と、 枚の皿 (初期状態ではすべて空) がある。これらを使ってゲームをする。先手と後手が交互に以下のように手を打つ。 (コインが入った袋が 1 つ以上存在するとき):コインが入…
これはマジで天才やと思うやが... いや本当にどこから Grundy 数を導けるのか、わからぬ... 問題へのリンク 問題概要 頂点数 のグラフが 3 つ与えられる。それらのグラフのカルテシアン積を考える。この頂点数 のカルテシアングラフの独立集合のうち、以下の…
すごく面白かった! 問題へのリンク 問題概要 個の袋があって、それぞれには 激辛バナナが 本 美味しいバナナが 本 がある。先手と後手が以下のことを交互に行う。 激辛バナナを 0 本または 1 本取り出す 美味しいバナナを好きな本数だけ取り出す ただし、激…
ふと TL に出してみた。絶対既出だと思ったから流したけど、どこかにあるかな...??? アイディア自体は SRM 309 DIV1 Hard StoneGameStrategist POJ 1704 Georgia and Bob (蟻本の例題) と同じものだったりする。むしろ問題に対してある種の同型変換を施す…
面白かった 問題へのリンク 問題概要 Nim の「石が 個しかとれないバージョン」を考える。 ただし勝敗の決まり方が、「先に石を取れなくなった方が負け」ではなく「先にいずれかの山の石の個数を 0 にした方が負け」である。 制約 考えたこと 一瞬逆形かと思…
staircase nim の流れで 問題へのリンク 問題概要 個の石の山が左から順に一列に並んでいて、各山には 個の石が積まれている。初期状態では を満たしている。今先手と後手が交互に 石が 1 個以上ある好きな山を 1 つ選んで 何個かの石を取り去る ただし とい…