子どものころに遊んだことがある、指を当てて数字を増やすゲーム(マッチ・グリンピース・戦争というらしい)の最適戦略が気になったので解きました。分裂なし消滅なし、指の数がN丁度になったらその手は消滅、Nを超えた場合、過ぎた分の本数になる、というルールです。

 2進数の場合(指の数が2本になると手が消滅する)
 先手必勝

 3進数の場合(指の数が3本になると手が消滅する)
 後手必勝

 4進数の場合(指の数が4本になると手が消滅する)
 先手必勝

 5, 6, 7, 8, 9, 10進数の場合
 ループ(引き分け)

 という結果になるようです。全数探査のようなもので求めました。
 勝ち確定(自分の手が生き残っていて、相手の手が全て消滅している)や負け確定のときをまず初期値として代入して、任意のパターンから派生される次のパターン(複数)の勝ち負けのチェックをして、勝ち負けがついてるならそのパターンの勝ち負けをつける、というアルゴリズムでやりました。

 割と驚きなのが5進数ではループ構造になるという点でした。最適行動を取れば勝てると思っていたんですが。
 この程度でも組み上げるのに地味に時間がかかったのでまだまだです。なおいつものごとく掘木さんのアルゴリズムを参考にしました。
2014.03.11 検証結果
 orz

fact1and2.png

 上が自作、下がboostライブラリの多倍長整数を用いています。(下に書いてある数値 × 50)!の実行速度が左です。だから(1500 × 50)!の計算時間が自作は30秒, boostは2秒くらいです。自作したやつがゴミすぎて泣けます。

 これだけではboostのほうが分かりにくいので、boostのほうだけを載せておきます。

fact2.png

 ……みんなも多倍長整数を自作するときは気をつけましょう!
 zzzです。
 「まともな」任意精度多倍長整数が欲しくて欲しくて色々と調べた結果、boostライブラリに任意制度多倍長整数がありました。boostならまともだろうと思うのでこれを使いましょう。DL、インストール方法は

https://sites.google.com/site/boostjp/howtobuild

 ここを見ればわかります。なお

http://www.kmonos.net/alang/boost/install.html

 によれば多倍長整数だけを使う分にはインストールの必要もありません。
 さらにライセンスもかの有名なgmpのLGPLよりもはるかに緩やかです(gmpのLGPLでも問題ない場合はgmpを使うべきだと思います。安心信頼の実績を誇るので)。具体的には

http://www.freeml.com/cppll/5777

 あたりにライセンスの日本語訳が書いてました。(ちゃんとした方がちゃんとしたものを作るなら、英語のほうも読んでください)
 多倍長整数の使い方は

https://sites.google.com/site/boostjp/tips/multiprec-int

 にあります。

 実は以前自作したんですが、あまりに遅いので任意精度の整数を用意した段階で面倒になって放置してたんですよね……。せっかくなので次は自作とboostライブラリとの計算速度を測ってみます。
KOMARIです。

近況:

ツクーレなんてなかった。

ラテールとかいうMMORPGはじめました。

解体ゲーやりまくったが、性に合わないみたいだ。

DIVINAやってましたが、性にあわないのでやめた。最初はそこそこ楽しめてたけど、ある程度いくと…。

プログラムはなにもやってません、完全放置

・体調わりー。

まあ、とりあえずUFO頑張って作ってみる。