はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるゲーム問題まとめ [Nim,Grundy数,後退解析,ミニマックス法]

ゲーム問題を解決する手段

  • Nim
    • 「N個の石山があり、交互に山から石を任意個取っていく。先に取れなくなったほうが負け。」
    • 各石山の個数をx[i]個とすると、勝敗は各山の個数を全てxorした値を見れば分かる。全てxorして=0なら先手は負け、!=0なら勝ち
    • Nimの派生
  • Grundy
    • 2人でやるようなゲームではGrundy数に帰着させることでNimの原理で解ける場合がある
    • Grundy数を以下のように定める
      • 負け状態のGrundy数は0
      • ある状態のGrundy数はそこから遷移可能な状態のGrundy数の中で最小の非負整数
    • grundy数とNimにおける石の数は同じ意味
    • 高さLの完全二分木のgrundy数はL&-L
    • 規則性
      • ある周期になっている
  • 後退解析、バックトラック 参考
    • 状態の遷移先に負け状態が1つでもあれば、相手を負けにできるので勝ち状態
    • 逆に遷移先が全て勝ち状態ならば、自分は負けるしか無い
  • 特殊な勝ち負け
    • 偶奇を使う
    • 相手の行動を真似ると負けない
      • 例えば、点対称に同様に置いていくと必ず置けるから、先手が置けるなら後手が必ず置けるので、後手必勝
  • ミニマックス法
    • 自分は利得を最大化し、相手は利得を最小化する

【発展的話題】Misere Nim

最後に石を取ると負けとしたNimのこと。よく分かる解説。
http://sigma425.hatenablog.com/entry/2014/12/07/132702
http://winjii.hatenablog.com/entry/2016/05/29/143653
簡単には、

  • 積まれている石の数が2以上のものがあれば普通のNim
  • 全部1の場合は山の偶奇によって勝敗が分かる

実装

int N; cin >> N;
int g = 0, ma = 0;
rep(j, 0, N) {
	int s; cin >> s;
	g ^= s;
	ma = max(ma, s);
}

if (ma == 1) {
	if (N % 2) printf("Second\n");
	else printf("First\n");
} else {
	if (g != 0) printf("First\n");
	else printf("Second\n");
}

競技プログラミングにおける動的計画法問題まとめ

動的計画法をまとめたもの

入門者向け

  • まずは「最大最小系」「yes/no系」「組み合わせ系」
  • 基礎はこことかこことかこことかで勉強しよう
  • ループで書くか、再帰関数かというのがあるが、こっちの方が書きやすいとかがあったりするので、どちらも書けるようになるのがオススメ

テク一覧

1. オートマトン上でDPする手法がある
2. 選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする
3. 状態が全部必要ないので状態数が削減できる
4. 正しい括弧列(dyck列)の数え上げはカタラン数を関連がある 必要な問題 解説
5. dp[L][R][sm]をやる時は答えを更新していくことでdp[L][sm]だけで済む場合がある
6. 隣り合う要素の更新を入れることで最近だけの更新を考えるだけで良くなる
7. 尺取り法を応用した更新最適化がある
8. メモリが少ない場合での復元には再帰を使うテクがある
9. 区間を添え字として持つDPがある
10. 【箱根DP】2つの順列の対応付けを行う典型
11. 文字列の部分列の個数を添え字に持つ典型
12. 縦と横は独立に計算できるため、O(WHN)をO(WN+HN+WH)にできる
13. 添字が負数になる場合は添字+baseをして、0をbaseにして使う
14. 境界線をうまく決めることで状態をまとめていく chokudaiさんの解説放送からの知見
15. 負の数を経由することで最適解が得られることがあるような問題は、最大最小の両方を保持しながらDPしていく
16. 配列を使い回すことでメモリ使用量を節約する(500^3は256MBに乗らない)
17. 遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる
18. 全体で遷移数がそんなに多くないことを見抜く
19. 配るDPを貰うDPに直してデータ構造で更新最適化
20. 【編集距離】編集距離の計算は、2つの文字列の添字を持つDPでできる

以下DPの問題(適当に分類、結構難しいのも含まれる)

最大最小系

yes/no系

組み合わせ系

雪の足跡 [yukicoder 340]

問題

https://yukicoder.me/problems/no/340

W×Hの盤面があり、N人の人がそこを通る。
i番目の人はM[i]回移動していて、移動先はB[i][j]->B[i][j + 1]である。
移動元と移動先はw + h * Wで表記されていて、距離が1とは限らない。

その移動後に(0,0)から(W - 1, H - 1)へN人が移動した方向と同じ方向に移れるとしたときの最短距離を求めよ。

1 <= W, H <= 10^3
0 <= N, M[i] <= 10^3
0 <= B[i][j] < W * H

続きを読む

競技プログラミングにおける2-SAT問題まとめ

2-SATとは

  • 「x ∧ y」の選言の充足判定をする 解説 コドフォ記事
  • 2-SATはSCCで解ける
  • ダメな組合せが見つかったときに制約を作る

競技プログラミングにおけるマージテク問題まとめ

マージテク

  • 正式名称、データ構造をマージする一般的なテク
  • 集合をまとめる時に大きい方に小さい方を移動させることでマージさせると計算量がならしO(logN)
  • 発祥の地
  • 併合(マージ)可能なheapをmeldable heapといい、実装の1つとしてマージテクを使うものがある(O(log^2N),Skew HeapだとO(logN))
  • 複数配列を全部FFTで畳み込む時にマージテクっぽい技を使うときがある こっちに書いた

問題

木DPっぽいやつをマージテクで高速化

  • CSAcademy Uniform Trees
  • ECR2 Lomsat gelral 解説1 解説2 解説3
  • ARC086 Smuggling Marbles (木のマージテクだけどO(N)になる)
  • CF221 Tree and Queries 解説1 解説2
    • ある色の頂点数がx以上の色の数を数えるdpのマージが、一見、マージテクになっていないように見えるが、ある色に対してマージ元にi個、マージ先にj個あった場合に[i+1,i+j]に+1をしていくのだが、この個数を全て足すとマージ先の頂点数と等しくなる
    • その為、マージ先の頂点数を別途数えて、その数を見てマージテクをやろう

【発展的話題】Sack (dsu on tree)

競技プログラミングにおける全方位木DP問題まとめ

全方位木DP

違うけど方針が似ている問題