先日、@Shindo200 さんと AtCoder の問題をペアプロをしていたのですが、#013 C 「笑いをとれるかな？」では解答者のソースコードを読んで勉強したのでメモ。石取りゲームの解法を知っているかどうかがポイントのようです。
[toc]
問題
問題は以下の通りです。詳細は#013 C 「笑いをとれるかな？」をご覧ください。
デビュー1年目の若手芸人「あっとこーだー」の高橋くんと青木くんは、地方ローカル番組に出演することになりました。この番組では「ドキドキ☆ハバネロゲーム」というゲームが人気です。以下が「ドキドキ☆ハバネロゲーム」の内容です。高橋くんと青木くんはリアクション芸が苦手なので、ハバネロが含まれた部分を食べてしまうと視聴者の失笑を買うことはわかっています。そのため、この2人は相方にハバネロを食べさせることで自分がすべることを全力で回避しようと考えています。 そこで、高橋くんと青木くんは相方に知られないように番組のプロデューサからハバネロの位置をこっそりと聞き出しました。 この2人が「ドキドキ☆ハバネロゲーム」において最善手を繰り返すとき、先にハバネロを食べてすべってしまうのはどちらでしょうか。
- 参加する2人はお互いに直方体の豆腐を切り取って、切り取った部分を食べます。
- ハバネロが含まれる部分を食べたほうが負けです。
- 高橋くんと青木くんはそれぞれ 1 回ずつ交互に切り取ります。
- この豆腐のある部分にはハバネロが仕掛けられています。
- 豆腐は複数存在することがあります。
- 全ての豆腐にハバネロが必ず仕掛けられています。
ずいぶん凝った設定ですね。問題の続きです。
あなたは神の視点から、この滑稽な2人の行く末を高橋くんだけに教えることにしました。なお、先攻は高橋くんで、豆腐の切り方は以下の通りです。
- 切り取り方は水平に 3 方向から切り取ることができます。つまり、斜めに切ることはできません。
- 豆腐の1辺の長さが必ず整数になるよう切断します。
- 例として、 2*2*2 の豆腐の切り方の一例を示します。
解説
問題を読んだ時点で石取りゲームの解法が思いつくことが大前提のようです。
石取りゲームの解説は 数学遊園地 ANNEX「石取りゲームの必勝法」で詳しく解説されています。○×ゲームを少し変えたようなゲームです。以下に石取りゲームの説明を引用します：
まず、石取りゲームのルールを説明しましょう。 石を下図のように何列かに分けて並べます。 １：○○○○○○○ ２：○○○○○○○○○ ３：○○○○○○ ４：○○○○○○○○
- 2人のプレイヤーがかわるがわる石を取っていき、最後に全部の石 を取った方が勝ちです。
- 石は、一回で１つの列からだけ取ることができます。１列であれば 何個取ってもかまいません。
- パスはできません。必ず、１個以上の石を取らなければいけません。
石取りゲームは二人零和有限確定完全情報ゲームとも呼ばれていて（長い…）、Wikipedia が詳しいです。この二人零和有限確定完全情報ゲームは、
理論上は完全な先読みが可能であり、双方のプレーヤーが最善手を打てば、必ず先手必勝か後手必勝か引き分けかが決まる
とのことで、石取りゲームにももちろん必勝法があります。
石取りゲームの必勝法
石取りゲームの必勝法は、各列の石の数を二進数で表し、繰り上がりなしで足し合わせた（排他的論理和を取った）結果が0であれば後手必勝、0以外であれば先手必勝となります。
ゲーム開始時に排他的論理和が0であるかどうかで勝敗が決まる訳ですが、これは以下の3つの命題から帰納的に導くことが出来ます：
- 最終的に石が0個になった場合にも当然成り立つ
- ゲームにおける石の数が狭義単調減少である
- 排他的論理和が0でない場合に、0にする石の取り方が必ず存在する
排他的論理和が0でない場合に、0にする石の取り方が存在することの証明
3つ目が少し不思議だったので、証明を考えてみました。排他的論理和の結果を用いると上手く証明できます。
- 列数 [latex]N[/latex] で各列 [latex]i[/latex] に対して石の数が [latex]s_i[/latex] だとすると、その排他的論理和[latex]X[/latex] は [latex]X=s_1 \oplus s_2 \oplus \ldots \oplus s_N[/latex] と表せます。
- 排他的論理和 [latex]X[/latex] の最上位が [latex]j[/latex]ビット目だとして、[latex]j[/latex]ビット目が1である列を任意に選択します。ここでは簡単のため、1列目が該当するとしましょう。
- 1列目の石の数[latex]s_1[/latex]と[latex]X[/latex]の排他的論理[latex]Y=s_1 \oplus X[/latex]を取ると、[latex]s_1, X[/latex]のどちらも[latex]j[/latex]ビット目が1であるため、[latex]Y
- このとき、[latex]Y=s_1 \oplus X[/latex] だったので、以下が成り立ちます：
- 以上より、[latex]Y=s_1-Z[/latex]となる数[latex]Z[/latex]を1列目から選択でき、その排他的論理和が0となることが分かりました。
「ドキドキ☆ハバネロゲーム」が石取りゲームと同じ理由
「ドキドキ☆ハバネロゲーム」は豆腐が複数出てくるのが難解なように感じますが、石取りゲームで例えると、豆腐は6つの列に相当します。ハバネロを起点とし、[latex]x,y,z[/latex]軸で切るのかが3通りあり、ハバネロの座標の前と後ろのどちらで切るのかで2通りありますので、6列となります。ハバネロを食べない＝豆腐を削いでいく＝石を取っていく、と考えると、ハバネロを中心とした、各頂点までの石取りゲームと同義です。
1つの豆腐にハバネロが複数出てくる場合も、豆腐を切った結果にハバネロが含まれていてはいけないため、各[latex]x,y,z[/latex]軸でハバネロの座標の最小値と最大値の間で豆腐を切ることは出来ません。つまり、豆腐の中のハバネロを最も小さく覆う立方体で切断することは出来ないため、このハバネロの座標の最大値と最小値を求める必要があります。
解答プログラム
何人かの解答者の解答を参考にし、理解のためのリファクタリングをさせて頂きました。今回の問題で疑問に思った方がいればご覧頂ければと思います。（ツッコミもお待ちしてます）
今回はハバネロを食べてしまうと「負け」なので、上で説明したルールの勝ち負けとは逆になっています。
変数名のリファクタリング、ハバネロを覆う立方体の計算に積極的に配列を用いるようにしたこと、ハバネロを覆う立方体の計算で明示的に min と max 関数を用いるようにしました。
（本当はインプット処理をまとめられれば良かったのですが、ループ処理が少し面倒になるのでやめておきました。。）
num_of_tofu = gets().chomp.to_i
winnable = 0
num_of_tofu.times do
tofu = gets().chomp.split(/\s/).map(&:to_i)
num_of_habanero = gets().chomp.to_i
habaneros = []
num_of_habanero.times do
habaneros << gets().chomp.split(/\s/).map(&:to_i)
end
// 原点から最も近い、ハバネロを覆う立方体の座標
min_from_o = []
// 原点から最も遠い、ハバネロを覆う立方体の座標
max_from_o = []
// 原点から最も離れた豆腐の頂点から、ハバネロを覆う立方体への相対座標
min_from_vertex = []
for k in 0..2
min_from_o[k] = habaneros.map{|habanero| habanero[k]}.min
max_from_o[k] = habaneros.map{|habanero| habanero[k]}.max
min_from_vertex[k] = (tofu[k]-1) - max_from_o[k]
end
// 石取りゲームの解法を用いる
winnable = (min_from_vertex + min_from_o).inject(winnable, &:^)
end
if winnable == 0
puts "LOSE"
else
puts "WIN"
end
競技プログラミングは仕事で使うプログラミング能力とは少し違うので、たまに解いてみると面白いのですが、今回の問題はどう解けばよいのか分からず詰まってしまったので、合わせて石取りゲームの解法などを勉強しました。
証明も、非常に簡単なものですが学生以来に自分で考えてみたので、よい頭の体操になりました(^_^; 何かの参考になれば幸いです。
