読者です 読者をやめる 読者になる 読者になる

/home/cympfh/

はてなブログはクソなのでやめます => https://hackmd.io/s/SyQBwu6Kg#

N言っちゃダメゲーム - yukicoder

プロコン

Mon Feb 22 23:01:59 JST 2016

No.8 N言っちゃダメゲーム - yukicoder

http://yukicoder.me/submissions/77454

石取りゲーム風に言い換えると、 "N 個の石があって 1 個から K 個の範囲で石を取る. 最後の 1 つを取ったら負け". いわゆる Nim の逆形.

後攻必勝の時に限り 0 になるようにグランディ数を決める. 局面の状態を山に残ってる石の数とする.

K=3 のとき:

 P | 1 2 3 4 5 6 7 ... 
 g | 0 1 2 3 0 1 2 ... 

(Markdownの表記表、ブレすぎてて嫌い)

 g(P)=(P-1) \bmod (K+1) って予想が付いた.  g(P) \ne 0 \iff 先手必勝

No.249 N言っちゃダメゲーム (2) - yukicoder

http://yukicoder.me/submissions/77473

かなり悩んだ. 何かのDPをするのかと思った. 負けた人は次のゲームで自由に先攻後攻を選べる、の意味は、勝ち負けを自由に選べるというだけの意味だった. 選ぶ側としてはわざわざ負ける理由が無いので結局、互いに勝ちを取り合って、公平にゲーム数を分け合うだけ.