C - 笑いをとれるかな? Editorial by maspy
まず,ひとつの立方体に注目します.
ハバネロのある \(x\) 座標の最小値を \(x_1\),最大値を \(x_2\) とします.\(y_1, y_2, z_1, z_2\) なども同様に定めます.
立方体をその座標により,\([a_1,a_2] \times [b_1,b_2]\times [c_1,c_2]\) などと書けば,
- \([a_1,a_2] \supset [x_1,x_2]\) 等が成り立つような操作のみが合法である.
- \(a_1\) を増やす操作,\(a_2\) を減らす操作,\(b_1\) を増やす操作,\(b_2\) を減らす操作,\(c_1\) を増やす操作,\(c_2\) を減らす操作ができる.
となります.\(6\) つ組 \((x_1-a_1,a_2-x_2,y_1-b_1,b_2-y_2,z_1-c_1,c_2-z_2)\) を考えると,ひとつの立方体に関するゲームは次のゲームに置き換えてよいです.
- 非負整数個の石が置かれた山が \(6\) 個ある.
- 各プレイヤは,ひとつの山から正整数の個数の石を取り去ることができる.
- 操作できなくなったプレイヤが負け.
すると,立方体が \(N\) 個ある状況は次のように言い換えられます.
- 非負整数個の石が置かれた山が \(6N\) 個ある.
- 各プレイヤは,ひとつの山から正整数の個数の石を取り去ることができる.
- 操作できなくなったプレイヤが負け.
これは,ニムのゲームという有名問題で,石の個数すべての xor により勝敗判定ができることが知られています.
posted:
last update: