日記 (2018 年 3 月 13 日)

一昨日の話ですが ARC091 に出てきました。 結果は、 3 問正解 1400 点で 834 人中 226 位でした。 レートは 1198 (緑) に増加しました。 もうこれ水色ってことで良くない?

さて、 ARC091 の F 問題について簡単にまとめておきます。 本番では時間がなくて考えることもできず、 終わった後に考えても解き方が分からず、 解説を見たら知らないテクニックが使われていました。 問題はこちらです。

場の状態を交互に変化させていくゲームがあって、 状態をこれ以上遷移できなくなったら負けとします。 これを両者が最善を尽くしてプレイするときに、 どちらが勝つか判定する問題です。 これを判定する最も愚直な方法は以下のようなものでしょう。 それぞれの場の状態 P に対し、 win もしくは lose の値をとる w(P) を以下のように定めます。

これによって初期状態 P0 に対する w(P0) を求めて、 それが win なら先手の勝ちで lose なら後手の勝ちとなります。

この方法は分かりやすいですが、 計算量が大きいので複雑なゲームには向きません。 そこで、 それぞれ状態 P に対し、 今度は以下のように定まる非負整数 g(P) を考えてみます。

すると、 初期状態 P0 に対する g(P0) を求めて、 それが 0 以外なら先手の勝ちで 0 なら後手の勝ちとなります。 実際、 少し考えれば w(P) を求めるのも g(P) を求めるのも同じことだと分かるので、 これは当たり前です。 ちなみに、 この g(P) は 「P のグランディ数」 と呼ばれます。

さて、 これだけでは実質最初のアルゴリズムと何も変わってないので、 グランディ数の良さは分かりません。 グランディ数は、 ゲームがたくさんある場合に真価を発揮します。 状態を遷移させるゲームが独立に複数個あり、 各プレイヤーは毎ターンにどれか 1 つのゲームを選んでその状態を遷移させることを考えましょう。 全てのゲームで状態遷移ができなくなったら負けです。 この場合にどちらのプレイヤーが勝つかは、 各ゲームの初期状態でのグランディ数を独立に求め、 それらのビット排他的論理和を計算することで判定できてしまいます。 すごくない?

ということで、 今回の問題では、 それぞれの山に対してグランディ数を求めれば良いことになります。 整数 K が定まっている山に石が A 個ある場合のグランディ数を g(A,K) と書くことにしましょう。 上に書いた導出方法の通りに愚直に計算すると計算量が大きくてダメなので、 少し考える必要があります。 実際に少し考えると、 以下のことが分かります。

ただ、 この通りに実装すると微妙に TLE します。 これを回避するため、 上の箇条書きの 2 番目の項目の漸化式において q+1 をひくわけですが、 q が変わらないうちは一気にひいてしまうことにします。 これで全てのテストケースに通るようになります。

ということで、 以下がうまくいくプログラムです。

public void run() {
BetterScanner scanner = new BetterScanner(System.in);
int n = scanner.nextInt();
int result = 0;
for (int i = 0 ; i < n ; i ++) {
int a = scanner.nextInt();
int k = scanner.nextInt();
result ^= grundy(a, k);
}
if (result == 0) {
System.out.println("Aoki");
} else {
System.out.println("Takahashi");
}
}
public int grundy(int a, int k) {
while (true) {
int q = a / k;
int r = a % k;
if (r == 0) {
return q;
}
// q が変化しなくなるまでの分を一気にひいてループ回数を減らす
a -= (q + 1) * ((r - 1) / (q + 1) + 1);
}
}

グランディ数を効率的に求める方法はたぶんその都度考えないといけないので、 まあ、 がんばろう。