472.1

900のときは600をやる方針。

250

整数から、4のべき乗を取り除く作業を交互にやって、最後に全部取った方が勝ちというゲームの勝者を判定せよ、という問題。

典型的なNimなので、どうやって相手をはめるか、というお話。4のべき乗は法5を見ると+1,-1しか取らないのと、終了状態が0なのと、+1の手と-1の手の打てる回数が余り離れていないのと、でうまくいく。言われてみればその通り、な問題。

600

N枚のカードがあり、表面と裏面にそれぞれ、1からNまでの異なる数字が書かれている。カードの構成が与えられるので、好きなように裏返しを許可して並び替えた時、出てくる数字のパターンは何通りか、という問題。

取り敢えず、あるカードから、裏面を見てそれと等しい表面のカードを探す、という処理を繰り返す。これにより何枚かのカードでループが発生し、それらにより作ることのできるパターンは他のカードとは独立であることが分かる。他のカードのグループとマージする際には、A枚とB枚のマージならA+B枚並べるうち、A枚を選択する配置パターンがある。つまり、個々のグループの並べ方さえ決まれば、マージは簡単にできる。

次にグループ内での並べ順を考える。N枚のグループの場合2^N通りの裏表の選択ができるが、全部裏返すと同じものができてしまう。あるカードを裏返して、それと同じ値が書かれているものを裏返さない、ということをやると同じ数字が2枚ある状況ができる。(実際は連続してK枚裏返すと、一組同じ数字ができることになる。)これを整理すると、1組同じものはNから1個選ぶというのと、それを反転させたもの、2組同じものはNから2個選ぶというのと、それを反転させたもの...、という風になるはず。(実際にテストしてないからなんとも...。)

900

見てない。