日記 (2018 年 3 月 13 日)
一昨日の話ですが ARC091 に出てきました。 結果は、 3 問正解 1400 点で 834 人中 226 位でした。 レートは 1198 (緑) に増加しました。 もうこれ水色ってことで良くない?
さて、 ARC091 の F 問題について簡単にまとめておきます。 本番では時間がなくて考えることもできず、 終わった後に考えても解き方が分からず、 解説を見たら知らないテクニックが使われていました。 問題はこちらです。
場の状態を交互に変化させていくゲームがあって、 状態をこれ以上遷移できなくなったら負けとします。
これを両者が最善を尽くしてプレイするときに、 どちらが勝つか判定する問題です。
これを判定する最も愚直な方法は以下のようなものでしょう。
それぞれの場の状態
から状態の遷移ができない場合はP w ( P ) = lose から遷移できる状態P でQ なるものが存在すればw ( Q ) = lose w ( P ) = win から遷移できる状態P が全てQ なるならばw ( Q ) = win w ( P ) = lose
これによって初期状態
この方法は分かりやすいですが、 計算量が大きいので複雑なゲームには向きません。
そこで、 それぞれ状態
から状態の遷移ができない場合はP g ( P ) = 0 - 上記以外の
に対するP は集合g ( P ) に属さない最小の非負整数{ g ( Q ) ∣ Q は P から遷移できる状態 }
すると、 初期状態
さて、 これだけでは実質最初のアルゴリズムと何も変わってないので、 グランディ数の良さは分かりません。 グランディ数は、 ゲームがたくさんある場合に真価を発揮します。 状態を遷移させるゲームが独立に複数個あり、 各プレイヤーは毎ターンにどれか 1 つのゲームを選んでその状態を遷移させることを考えましょう。 全てのゲームで状態遷移ができなくなったら負けです。 この場合にどちらのプレイヤーが勝つかは、 各ゲームの初期状態でのグランディ数を独立に求め、 それらのビット排他的論理和を計算することで判定できてしまいます。 すごくない?
ということで、 今回の問題では、 それぞれの山に対してグランディ数を求めれば良いことになります。
整数
- 非負整数
に対してq g ( q K , K ) = q - 非負整数
と整数q に対してr ( 0 < r < q ) g ( q K + r , K ) = g ( q K + r − q − 1 , K )
ただ、 この通りに実装すると微妙に TLE します。
これを回避するため、 上の箇条書きの 2 番目の項目の漸化式において
ということで、 以下がうまくいくプログラムです。
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);
}
}
グランディ数を効率的に求める方法はたぶんその都度考えないといけないので、 まあ、 がんばろう。