topcoderに書いてあるWL-Algorithm(要はゲーム系の問題で、後ろから探索するもののうち単純に再帰して深さ優先探索していくやつ)についての備忘録です。*1深さ優先探索、メモ化再帰とpythonについて知っていれば、この記事は読めます。競技プログラミングにおいて、ゲーム系の問題は、ARC038の解説でもあるように、大体は以下の3つで解けると言われている。後ろから探索するGrundy数を求めるadhocな必勝法を見つけるこの記事では、1の後ろから探索する場合で、特に深さ優先探索していくものについて考える。Algorithmここで行うゲームとは2人で行う現在の状態から遷移できる状態がどのターンでも両者ともわかる終了状態で勝ち負けが決まるというものである。トランプの大富豪はここでいうゲームには入らない。このアルゴリズムでは、関数isWinningを定義し、初期状態を引数としてisWinningを計算する。現在の状態(state)で、勝つ(True)か負ける(False)かを返すこの関数は以下のように動作する。現在の状態が終了状態なら負け*2現在の状態から遷移できる状態を全て求める全ての状態についてisWinningを計算する3で計算したisWinningで、1つでも負け(False)があれば勝ち(True)を返すそれ以外は負け(False)を返すpythonで書くと以下のようになる。負けこのアルゴリズムを使うときに考えるべきは、以下の3つであるゲームの初期状態は何かゲームの終了状態は何か現在の状態から遷移できる状態を全て列挙できるかまた、メモ化を行うときは以下のようになる。AtCoderH行W列のマス目と駒が1つ与えられ、2人で順番に駒を動かしていく。1)にあり、いくつかのマスには障害物がおいてある。j+1)の3つの場所に移動可能である。移動先の場所に障害物がある場合は移動できない。与えられた盤面で、先手(First)と後手(Second)のお互いが最善を尽くしたとき、どちらが勝つか求めよ。Algorithmを用いる。(簡単のため、0-indexとする)ここでいう状態とは、マスの座標のことである。j)に障害物が置かれるかである。この場合、相手が移動できない位置に駒を移動させているため、勝ちである。j+1)の3つである。これを元に、isWinning関数を書くと以下のようになる。Falseメモ化を行う場合は以下のようになる。False最後に自分のような競プロ初心者はゲーム系の問題でよく出て来る(らしい)Grundy数とかいう大層なものの以前に、これが直感的に理解できないので書いて整理しておきたかった。nanikakaのAOJ航海日誌が詳しい。topcoderでいろいろなアルゴリズムについて解説しているので蟻本とあわせて読んでいきたい。(1)はてなブログをはじめよう!n_knuuさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。