Hatena::Grouptopcoder

nase@topcoder

 | 

2011-04-01

ゲームの必勝法系の問題について

12:53

topcoderをやっていて感じるのは、プログラミングコンテストに出題される問題のパターンの多様さ。

ちょっとやそっとでは「あ、これはこのパターンね」とならない。

少なくとも私はSRMに参加するたびに毎回知らないパターンの問題に頭を悩ましている。

それでも、少しでも問題をパターン化しておきたいと思うのは私のみではないだろう。

という前置きはいいが、最近一つパターンを覚えたので書いておく。

ゲームの必勝法や、勝敗判定をする問題で、探索空間が広く考察が必要になる系統について。

例えば、SRM493 Div1 Easy StonesGame

これは本番でずいぶん苦労したのだが、「一発で勝利する手以外は、相手に少なくとも指した手を打ち消す手が存在するため、勝ちにはならない」という当たり前の考察にたどり着いてからはすぐに解けた。

この考察はどうも定石のようで、最近2問例題を見た。

SRM216 Div1 Hard Roxor

SRM309 Div1 Hard StoneGameStrategist

さきほどの問題では引き分けがあるが、以下は引き分けのないゲームの場合で。

上記考察を書き直すと「打ち消し可能な手は勝敗判定で考慮する必要がない」となる。

注意する必要があるのは、打ち消し可能な手も勝ち手順中に出てくることはある、ということ。

勝ちの場合は辞書順最小な手順を返すというような問題の場合は、打ち消し可能な手も指してみる→勝敗判定という処理が必要になるけど、勝敗判定ルーチンの中では打ち消し不可能な手順のみを考慮すればよい。

Roxorの例題2がその例。

 | 
twitter ホーム 吉祥寺 わいわい将棋