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: