へなちょここーだー

プログラミング初心者がtopcoderなどの競技プログラミングに挑戦。勉強したアルゴリズムなどを書いていきます。現在topcoder緑でcodeforces青。どちらもDiv1昇格を目指しています。

Grundy数 その2

アルゴリズム

前回はGrundy数とは何かを説明しました。Grundy数に関する基本的な求め方は前の記事をご覧ください。augusuto04.hatenablog.com
ただ、これだけではあまり多くの問題に使えないのでもう少し発展的な使い方を紹介します。

Nim

私は知りませんでしたが、有名なゲームらしいですね。ルールは次の通り。

n個のコインの山があります。プレーヤーは１つの山を選んで、その山から1枚以上のコインを取り除きます。これを2人で交互に行い、取り除くコインがなかったらその時点で負けになります。
f:id:augusuto04:20150504000833p:plain
ここで、上のような場合を(4, 2, 1)と今回は表します。

とりあえず各山についてGrundy数を求める

まずは、各山についてGrundy数を求めます。
もし、0枚の山があるとするとここからは遷移できないのでGrundy数は0。
1枚の山からは0枚の山に遷移できるのでこれ以外で最小は1。
2枚の山からは0, 1枚の山に遷移できるのでこれ以外で最小は2。
このように、今回は山にあるコインの枚数とGrundy数は等しくなる。
つまり、今回の例におけるGrundy数は次の通り。

コインの枚数 4 2 1
Grundy数 4 2 1
全体について考える

では、今回は(4, 2, 1)と3つの山がありますが、この状態におけるGrundy数はどうやって求めればいいのでしょうか。結論からいいます。4 xor 2 xor 1を計算すればよいのです。つまり、この状態におけるGrundy数は7である。と言うことで今までのようにGrundy数が0より大きいので最適な行動をとれば先手の勝ちとなります。なお、xorってなんだって方はこちらをどうぞ。augusuto04.hatenablog.com
では、なぜこれでよいのでしょうか。(4, 2, 1)から遷移できるすべての状態おいて同じようにしてGrundy数を求めると次のようになります。

状態 Grundy数
(3, 2, 1) 0
(2, 2, 1) 1
(1, 2, 1) 2
(0, 2, 1) 3
(3, 1, 1) 3
(3, 0, 1) 2
(3, 2, 0) 1

このようにして、Grundy数が0になるような場合か必ず存在します。では、Grundy数が0である(3, 2, 1)からの遷移を次は考えてみます。

状態 Grundy数
(2, 2, 1) 1
(1, 2, 1) 2
(0, 2, 1) 3
(3, 1, 1) 3
(3, 0, 1) 2
(3, 2, 0) 1

このようにGrundy数が0になるような遷移は存在しません。前回と同じように次のことが言えます。

  • 自分の手番でGrundy数が0なら次の状態におけるGrundy数は必ず0より大きい。

→相手が最適な行動をとれば負け

  • 自分の手番でGrundy数が0より大きいならば次の相手の手番にGrundy数が0になる遷移を選べる。

→自分が最適な行動をとれば勝ち

思ったよりも書きたいことが多い・・・。次の記事で実際にコードを紹介して終了にします。augusuto04.hatenablog.com

Grundy数 その１

Grundy numberについての勉強をしたので、そのまとめ（自分用のメモでもある）。ちなみにNimberとも言うみたいですね。実際にいくつかのゲームを考えながら説明をしていきます。最後の結論まで少し長いです。

そもそもGrundy数ってなんだろう

具体例は後で出すとして、とりあえずGrundy数の求め方から紹介します。

ある状態におけるGrundy数はそこから遷移できる状態におけるGrundy数以外の最小の0以上の整数。
えーと・・・。これだけでは良く分かりませんね（笑）。じゃあ実際にあるゲームを考えてみます。

30を言ったら負けゲーム

以前、伊東家の食卓というテレビ番組で紹介されたゲームです。ルールは次の通り。

先手と後手が交互に1つ以上3つ以下の整数を1から順に30まで言っていく。
先手は1から初め、30を言った人が負け。
例えば、先手:1, 2, 3 後手:4 先手:5, 6 後手:7, 8, 9 ・・・と続けて30を言った人が負けです。

とりあえずGrundy数の求め方

このゲームにおけるGrundy数をまずは計算してみます。

次に言う数 1 2 ・・・ 22 23 24 25 26 27 28 29 30
Grundy数 1 0 ・・・ 0 3 2 1 0 3 2 1 0

まずは30から考えます。ここから遷移（たどり着く）数はないので最小の0以上の整数は0。
29からは30に遷移でき、このGrundy数は0である。よってこれ以外の最小の0以上の整数は1。
28からは29, 30に遷移でき、これらのGrundy数である1, 0を除く最小の0以上の整数は2。
27からは28, 29, 30に遷移でき、これらのGrundy数である2, 1, 0を除く最小の0以上の整数は3。
26からは27, 28, 29に遷移でき(3つまでしか数は言えないため30へは遷移できない)、これらのGrundy数である3, 2, 1を除く最小の0以上の整数は0。
これを繰り返し、すべてのGrundy数を求めます。

で、ここから何が分かるの？

実は自分の手番におけるGrundy数を見えると、そこからお互いが最適な行動をしたときの勝敗が分かるのです！Grundy数が0ならばそのときに手番の人は負けます。Grundy数が0より大きければそのときに手番の人が勝ちます。ではなぜなのでしょうか。次の２つの場合について考えます。

そこから遷移できる状態のGrundy数はすべて0より大きいです。

  • Grundy数が0より大きいとき

そこから必ずGrundy数を0にするように遷移出来ます。
つまりは次の画像のような状態になります。
f:id:augusuto04:20150503233056j:plainf:id:augusuto04:20150503233104j:plain
なので、Grundy数が0ならば相手が最適な行動をとれば負け、Grundy数が0でなければ自分が最適な行動をとれば勝ちなのである。よってこのゲームでは先手が必勝であることが分かる。

長くなってしまったので次の記事に続きます。
augusuto04.hatenablog.com

WL-Algorithm

アルゴリズム

AtCoderで出題されていて、topcoderでも紹介していたのでちょっとまとめてみました。2人が最適な行動を行ったとき、勝つか負けるかを判定する単純なアルゴリズムです。
WL-AlgorithmというとWang-Landau Algorithmを指すことが多いようなのですが、今回はtopcoderで紹介されていたこの名前で呼びます。

考え方

すごくシンプルな考え方です。

function isWinning(今の位置){
  for(現在位置からのすべての行動x)
    if(isWinning(x)は負け) return 勝ち;
  return 負け;
}
  • 相手を必ず負けさせるような手が存在するなら現在の位置では勝ち決定。

→isWinning(x)が負けのとき

  • そのような手がないないのであれば負け。

これを勝敗が決定する最後の手から考えていくと先手必勝か後手必勝かを判定出来ます。

実践例

今回はAtCoder Regular Contest 038のB-マス目と駒について考えます。
今の位置は(r, c)で表します(rは現在の行、cは現在の列)。現在位置からの全ての行動は(r + 1, c), (r + 1, c + 1), (r, c + 1)である(右、右下、下に移動可能)。するとコードは次のようになります。

string grid[]; //マス目の各列
int H, W;       //Hは行数、Wは列数
bool isWinning(int r, int c){
  if(r >= H || c >= W || grid[r][c] == '#') //この位置が盤外または障害物ならば勝ち扱い
    return true;
  if(isWinning(r + 1, c) == false)
    return true;
  if(isWinning(r + 1, c + 1) == false)
    return true;
  if(isWinning(r, c + 1) == false)
    return true;
  return false;
}

盤外と障害物の対処方法を加えていますがそれ以外は先ほどの考え方と変わりません。ただし、これだと計算量が多いのでメモ化をして改善したコードは次の通り。

string grid[MAX];
int H, W, m[MAX][MAX]; //mがメモ

bool isWinning(int r, int c){
  if(r >= H || c >= W || grid[r][c] == '#')
    return true;
  if(m[r][c] != -1)
    return m[r][c];
  bool result = false;
  if(isWinning(r + 1, c) == false)
    result = true;
  if(isWinning(r + 1, c + 1) == false)
    result = true;
  if(isWinning(r, c + 1) == false)
    result = true;
  return m[r][c] = result;
}

既に計算済みならばメモを残して再計算しないように工夫をしているだけです。

復習

AtCoder

AtCoder Regular Contest 038の復習完了。解説があるのがとてもありがたい！

マス目と駒

全探索→メモ化再帰というところまではすぐに思いついたのですが、そっか判定は結構単純ですね。

  • 今のマスが盤外or障害物→勝ち
  • 次の番の人が負ける→勝ち
  • 上記以外→負け

盤外と障害物の対処方法は問題で役立ちそうな考え方ですね。この問題はそろそろ解けるようにならねば。

他の2問はGrundy数とmin-max法を利用する問題でした。
もう少し勉強してから、今度まとめて見ようかと思います。

AtCoder Regular Contest 038

AtCoder

ゴールデンウィークはコンテストに集中するチャンス！
とウキウキでしたが惨敗でした。

A-カードと兄妹 100点

さすがにこのレベルの問題は簡単。

B - マス目と駒　0点

C - 茶碗と豆　0点

D - 有向グラフと数 0点

全部似たような問題なんですかね。3問とも2人でゲームをしてそれぞれが最適な行動をする問題でした。ちょっと調べてみてMini-Max法とかAlpha-Beta法が出てきたのでその辺りを勉強してみます。

ってな訳で209位で惨敗。ってか分からなさすぎて途中でやめてHackerRankの問題解いてました。そっちはだんだんとDynamic Programmingが理解できてきて解ける問題が増えています。

101 Hack April'15

HackerRank

勉強を始めてから約3週間、初めてコンテストに出場しました！
その結果がこちら。

Rat Race (Easy) 20/20点

a / bがintになることを忘れるという凡ミスをして最初は焦りましたが、楽勝！

Twisty Tuple (Moderate) 60/60点

最初は全探索を行ってタイムアウト。アルゴリズムを改善して正解。
こういう問題が解けると気持ちいいですね。

Contest Strategy (Difficult) 0/80点

結構時間を使って考えたのだが解けず。正直悔しい。

Grand Tour (Advanced) 3.85/100点

最近覚えた幅優先探索が使えそうだなと思ったけど実装できず、部分点だけで終了。

Introduction to Topology (Advanced) 0/120点

問題を読んだだけで解かず。

合計点は83.85点で122/ 812位でした。まだまだ勉強しないといけないですね。
ただ一ヶ月ほどでここまで来られたので、少し達成感はありました。次も頑張るぞ！

累乗計算の高速化

アルゴリズム

HackerRankのAntiPalindromic Stringsを解くときにどうしても累乗計算がO(n)になってしまいタイムアウトになってしまっていたところ、凄くキレイで高速なアルゴリズムを発見！
高速な累乗計算 - あどけない話
これを使ってみました。

単純なxのn乗をmを法として求めるアルゴリズム

long myPow(long x, long n, long m){
  long result = 1;
  for(int i = 0; i < n; i++){
    result *= x;
    result = result % m;
  }
  return result;
}

改善後のアルゴリズム

ここから、累乗計算の方法を改良していきましょう。その例として、{3^{19}}を計算してみます。

1. まずは19を2進法であらわす。
    {\begin{eqnarray} 19 &=& 2^0 + 2^1 + 2^4 \\ &=& 1 + 2 + 16 \end{eqnarray}}
2. これを利用して累乗を計算する。
    { \begin{eqnarray} 3^{19} &=& 3^{1 + 2 + 16} \\ &=& 3 \cdot 3^2 \cdot 3^{16} \end{eqnarray}}
3. これを計算できる漸化式を考える。
    {x^n = \begin{cases} (x^2)^{n / 2} &\text{if } n \text{ が偶数}\\ x \cdot x^{n - 1} &\text{if } n \text{ が奇数} \end{cases}}
4. この漸化式による計算を考える。
    { \begin{eqnarray} 3^{19} &=& 3 \cdot 3^{18} \\ &=& 3 \cdot (3^2)^9 \\ &=& 3 \cdot 3^2 \cdot (3^2)^8\\ &=& 3 \cdot 3^2 \cdot (3^4)^4\\ &=& 3 \cdot 3^2 \cdot (3^8)^2\\ &=& 3 \cdot 3^2 \cdot 3^{16} \end{eqnarray}}
いかがでしょうか。これにmを法にして解くという条件を加えて書いたコードは次の通り。

long myPow(long x, long n, long m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}

これでO(log n)になり、バッチリ解くことが出来ました。ただ、また新しい記事を発見。
累乗を求めるプログラムの速度計測 - ak毎日ブログ
どうやら再帰関数を使うと関数の呼び出しで遅くなるからfor文を使った方が速いらしい。なるほど、勉強になります。