ゲーム系問題のはなし
この記事はこのスライドの受け売りなので, ちゃんと知りたい人はこっちを読んでください。
はじめに
ゲーム系の問題は以下の三つに大別できます。
- 後ろから探索
- grundy数を計算
- adhocな必勝法を見つける
順番にみていきましょう
後ろから探索
単純にゲーム木を探索する方法です。制約があまりキツくない問題に使うことができます。まずこれから考えるのが良いでしょう。実装にはメモ化再帰やDPを使うことが多いです。例題
例題,例題2grundy数を計算
grundy数は不偏ゲームの状態に定義される数であり, その定義は以下の通りです。
- terminal positionではgrundy数は0
- それ以外では、その局面から１手で移動できる局面のgurundy数の集合に含まれない最小の自然数
このように定義すると、負け局面ではgrundy数は0、それ以外では正の自然数になります。
grundy数の重要な性質として、いくつかのゲームが合わさったようなゲームに対して、そのgrundy数はそれぞれのゲームのgrundy数の排他的論理和(xor)になることが挙げられます。
ad hocな必勝法を見つける
天才になってください。 とはいえこれだけだと僕のような凡人には厳しいのでいくつか考えるヒントを書いておきます。
- とにかく実験 全探索できる範囲で試してみましょう。規則性が見つかるかもしれません
- 相手と対称な動きをするのが最善
- 偶奇性を考える
- 必敗局面から必敗局面には移動できない
例題
例題1, 例題2, 例題3, 例題4その他
- 実はどう行動しても結果が変わらないという場合もある例題
- 最後の形をイメージする
半分全列挙のはなし
最近Atcoderの青difficulty問題を解き切ったので、それに絡めて記事を書いていこうと思います。初回は半分全列挙についてです。半分全列挙はその名の通り半分だけ状態を列挙する方法です。これだけだと何のことかわからないと思うので、例題を用いて考えてみましょう。 例題 パッと問題文を見るとDPが思い浮かぶと思いますが、制約をよく見るとX<109なので難しいです。一方、N<32と非常に小さいことに注目しましょう。ただし、荷物のあるなしの全ての状態を考えると232~109となり、間に合いません。そこで、荷物を半分づつグループに分けてそれぞれグループ１、グループ２と呼ぶことにします。簡単のためN=2nするととそれぞれのグループについてそこから何個か選ぶ組み合わせは2nなので全て列挙することができます。まずグループ１の状態を固定しその大きさをw1とします。すると問題の条件を満たすためには、グループ２から取ってきた荷物の重さの合計がw2 = W-w1となる必要があります。これを満たす選び方の数はグループ２の状態を全て列挙しているので簡単に求めることができます。
from bisect import * N, X = map(int, input().split()) w = [int(input()) for _ in range(N)] weight1 = [] for s in range(1<<(N//2)): res = 0 for i in range(N//2): if s & 1<<i: res+=w[i] weight1.append(res) weight2 = [] n = N-N//2 for s in range(1<<n): res = 0 for i in range(n): if s & 1<<i: res+=w[N//2+i] weight2.append(res) weight1.sort() weight2.sort() ans = 0 for w in weight1: l = bisect_left(weight2, X-w) r = bisect_right(weight2, X-w) ans+=(r-l) print(ans)
N~36の時はだいたい半分全列挙だと思いましょう。 類題
青diffまとめ
二分探索
pairs snuke the wizard nearest card game decrease sports festival 食塩水 高橋ノルム君 高橋君ボール 壁抜け 細長いお菓子
DP
payment swap and flip balanced path common subsequdnce we love abc mixing experiment 徒競走 経路 塗り絵 1 難易度 高橋くんの苦悩
数学
manymanypaths
包除原理
tree and constraints 11 すぬけ君の塗り絵
全ての場合の総和
fusion slimes change a little bit second sum cell distance 井井井 Minimum Sum
グラフの改造
shortest path on a line travel by car coins respawn saving snuuk score attack cosmic ray
適当な数の掛け算
cell inversion double landscape robot racing
二部グラフ
classified 3steps
操作
numbers on a circle digit sum replace contiguous painting 道路の老朽化対策について 駐車場
決め打ち
max gcd match matching various sushi equal cut range minimum queries integerotS moderate differences 3Nnumbers Colorful Slimes 語呂合わせ バレンタインデー ハイスコア
シミュレーション
do not duplicate roadwork frequency Greedy Customer へんてこ辞書
構築
xormatching tr/ee all your paths are different length gcd sequence lisdl wide flip construct sequence Tree Restoring
ゲーム
removing coins tozan and gezan alice&brown an ordinary game 倍々ゲーム 双子の丸ばつゲーム マス目と駒
半分全列挙
string coloring 無駄なものが嫌いな人
その他
enclosed all rem of sum is num digit sum replace two contest pure sorting a segment must be rectangular squirrel merchant absolute minima factorization rng10s rgb coloring worst case forest checker atcoder express build colorful hats meaningful mean closed room hamilton path rrBBnsformbbtion maximum aberage set boxes tournament tetromino tiles pair card Gr-idian MST いろはちゃんとマス目 トレジャーハント 経路 ドキドキデート大作戦高橋君 最短路問 高橋幼稚園 blue bird 多重ループ atcoder王国の交通事情 高橋くんときの直径 約数かつ倍数 菱形カウント データ構造 特別賞 大事な数なのでZ回書きました ョコレート 赤と黒の木 your numbers are xored 美味しいたこ焼き 子点と整数 派閥 風力観測 魂の帰る場所 ダブレット 節約生活 器物破損高橋くん
サピア＝ウォーフの仮説のはなし
最近Ted Chiangの"Story of Your Life"を読み終えました（原著で読んだら死ぬほど時間かかった）。色々調べたら「サピア＝ウォーフの仮説」というのが出てきたのでちょっと書きます。 サピア＝ウォーフの仮説は認識、思考は言語に強く依存するという仮説です。 SF界隈では有名っぽく、よくあるテーマのようです。確かに読んでる最中、伊藤計劃の「虐殺器官」を思い出しました（あれも言語が思考に影響を及ぼすという話でしたね）。現在は否定されてるらしいですが、SFのテーマとしてはロマンがあって面白かったです。
UnionFindの使いかためも
UnionFindはrootで各集合を代表させているので、root = U.find(a)で色々やる。
独立集合の数
a == U.find(a)なるaの時のみcnt+=1する
集合のサイズ
U.find(a)の時のsizeを取得
木のはなし
競プロで題材にされがちな「木」についてメモしておきます。
