初めに
今回は幾何とゲームのアルゴリズムをやります。
1. Nim
有名なゲームです。
石の山が何個かある。各山から任意個の石を交互に取っていって、取れなくなった人の負け
こういうゲームの問題は判定しやすい必勝パターンが存在し、その状態にはめる事で勝利する...って問題が多いです。例えば1, 2, 3石取りゲームだとmod 4から逃げられないので4の倍数以外だと必勝です。
さて、結果を書いちゃいましょう。各山の個数のxorを取った値が0で無いなら必勝です。思いつくのは難しいですが、知ってしまえば簡単です。
2. Grundy数
任意のゲームは盤面の状態を頂点とするグラフとみなす事が出来ます。基本的にそのグラフはDAGとなります(DAGとならないと無限ループが存在するので)。DAGは閉路の無い有向グラフの事です。
2人向けのゲームで、自分と相手で取れる行動が同じで、動けなくなった方が負けで、有限回で終了する(無限ループが存在しない)ゲームについて考えます。もし、状態数がそんなに多くないならば、再帰による全探索(一部メモ化が必要かも？)すれば解けます。これは本質的には動的計画法です。具体的には、各頂点に対して 操作している人が 負けるかどうかを調べます。次に有り得る遷移先の内、負けが1つでも存在すればそこに遷移すれば勝てます。そうじゃないなら負けです。
しかし、そんな問題出たとして400点くらいです。難しくさせ方には何通りかあって、お手軽にできるやつは 盤面を複数持って、最終的に勝つか負けるかを判定させる とかです(それ以外は必勝パターンを見つけるのが難しいとかになり、実験が必要になったり天才が必要になったりします)。さて、どうしましょうか。
最初に思いつくのは各盤面独立に判定させて何らかの方法で合わせる事ができないかでは無いでしょうか。結果を先に言うとこれは不可能です。2つの盤面の時、負け+負け=負け、勝ち+負け=勝ちですが、勝ち+勝ちは不定だからです。何故でしょうか。負けてもターンはズレないのですが、勝つ、つまり相手が操作出来なくなった時1ターンズレるからです。という事は負けという情報はそれで十分であるが、勝ちという情報はより詳しい情報が必要である事が分かりますね。
ここで天才が出てきます。n完全DAGを頂点数nでこれ以上辺を追加できないようなDAGとします。n完全DAGから1, 2, ..., n-1完全DAGに遷移できます。1完全DAGは頂点数1で、次の遷移が存在しない状態とします(少しだけ頭がこんがらがります)。すると、任意の異なる2自然数n, mに対して、n完全DAGとm完全DAGは同じパターンには成りえません(当たり前ですね)。n>mならnからはmに遷移できますがmからnは不可能だからです。逆に、任意のグラフはn完全DAGと同じ形となるnをただ一つ決める事が出来ます。
例えば今いる頂点から1, 2, 3, 4, 6, 8, 10完全DAGに遷移できるとします。この時このグラフは5完全DAGとみなす事が出来ます。それは、6, 8, 10完全DAGに遷移するメリットが皆無だからです。もしこのグラフが仮に5完全DAGだとして、その結果勝てるのパターンであるなら、6, 8, 10完全DAGに遷移すると相手は5完全DAGに遷移する事が出来、相手が勝ちます。逆に負けパターンならどうあがいても負けます。シンプルですね。
よりコンピュータが理解しやすい形で書くならば 遷移先にn完全DAGが存在しないようなnのうち最小のもの と書く事も出来ます。そして、ここまで理解出来たならこれはNimに帰着できる事も分かりますね。現状をまとめると、n(完全DAG)からn未満自然数に変化させる事が出来、最後に操作できなくなった方が負け。但し、Nimで計算できるようにするため-1する必要がありますが。
まとめると、 各グラフに対して非負整数を決めていく。最終状態は0で、それ以外の頂点は移動先の頂点の番号の中で存在しない最初の非負整数。そして各グラフの初期位置の数のxorを取り、0なら負けでそれ以外なら勝ち となります。ついてこれましたか？これがスッと理解できるなら賢いと思います。僕は理解できるまで時間かかりました。
yosupoさんのこのスライドを参考にしました。
3. 幾何
AtCoderで幾何の問題はあまりでません。よく出るのはICPCとかです。幾何ライブラリを整備するのはいいのですが、座標classとかを作るとICPCの時写経で死にます。ICPCの事も考えるなら、C++のライブラリにある複素数ライブラリを使うのがいいでしょう。
まずは計算誤差の話をしましょう。
#include<cstdio>
using namespace std;
int main() {
int cnt = 0;
for (double i = 0; i < 100; i += 0.1) {
cnt++;
}
printf("%d\n", cnt);
}
これ、何回実行されますか？1000回？答えは、僕のパソコンだと1001回でした。何故？？？そもそも大抵の10進数は2進数に直すと無限小数になります。正確には、有理数の形で表した時分母が
#include<cstdio>
using namespace std;
int main() {
double a = 10000000000;
printf("%lf\n", a*(a+1) - a*a - a);
}
これ何になると思いますか。0？僕のパソコンだと7168になりました。わお！桁が大きい掛け算をして、殆ど等しい値の引き算とかをすると、有効数字が一気に無くなります。あんまり競プロでは見ないけど、これはプログラマなら絶対知っておくべき話なので覚えておこう。
さて、話を幾何に戻すのですが、このページがとても参考になります。時間があればまとめたいです。
