G - Constrained Nim 2 Editorial by nok0
本解説では grundy 数 の理解を前提とします。知らない方は、以前のABC でも取り扱われていますのでそちらを参照ください。 (類題 : ABC255-G)
ゲームの問題では、実験をしてみるのが有効な場合が多いです。
この問題でも実験をしてみると、\(x\) の grundy 数 \(f(x)\) が以下であることが予想できます。
\[\lfloor \frac{x\bmod {(L+R)}}{L}\big\rfloor\]
この予想が正しいとすれば、本問題は \(\mathrm{O}(N)\) で解けます。(実装例は後述)
以下ではこの予想が正しいことを証明します。
(1) \(x < L+R\) のとき
\(0\leq x <L\) では操作ができないので \(f(x)=0\) です。
\(L\leq x <2L\) では \(x < L+R\) より \(x-R < L\) なので grundy 数が \(0\) の局面に遷移できます。また \( x - L < L\) より grundy 数が \(1\) の局面には遷移できません。よって \(f(x)=1\) です。
\(2L\leq x <3L\) では \(x < L+R\) より \(x-R < L\) なので grundy 数が \(0\) の局面に遷移できます。さらに \(2L \leq x < 3L\) より \(L\leq x - L < 2L\) より grundy 数が \(1\) の局面にも遷移できます。また \( x -L<2L\) より grundy 数が \(2\) の局面には遷移できません。よって \(f(x)=2\) です。
以上の議論を同様に繰り返すことで、\(x<L+R\) では \(f(x)=\lfloor \frac{x}{L}\big\rfloor\) が成り立つことが示せました。
(2) \( L+R\leq x < 2(L+R)\) のとき
\(L+R\leq x < L+R+L\) のとき、 \(L\leq x-R<2L\) 、 \(R\leq x-L<L+R\) より grundy 数が \(0\) の局面に遷移できないことが分かります。よって \(f(x)= 0 \) です。
\(L+R+L\leq x < L+R+2L\) のときも同様の議論により grundy 数が \(0\) の局面には遷移できるが \(1\) の局面には遷移できないことがわかります。よって \(f(x)=1\) です。
同様の議論が \( L+R\leq x < 2(L+R)\) を満たす全ての \(x\) について成り立ちます。よって \( L+R\leq x < 2(L+R)\) では\(f(x)=\lfloor \frac{x\bmod {(L+R)}}{L}\big\rfloor\) が成り立ちます。
(3) 一般の場合
\(2(L+R)\leq x\) の場合、grundy 数 \(f(x)\) は今回の場合 \(f(x-R),f(x-R+1),\ldots,f(x-L)\) にしか依存しないことを用いると、(2) より一般の場合について \(f(x)=\lfloor \frac{x\bmod {(L+R)}}{L}\big\rfloor\) が成立していることが言えます。
実装例(C++):
#include <bits/stdc++.h>
using namespace std;
int f(int x, int l, int r) {
return (x % (l + r)) / l;
}
bool solve(vector<int>& v, int l, int r) {
int fold = 0;
for(const auto u : v) fold ^= f(u, l, r);
return fold != 0;
}
int main() {
int n, l, r;
cin >> n >> l >> r;
vector<int> a(n);
for(auto& v : a) cin >> v;
cout << (solve(a, l, r) ? "First\n" : "Second\n");
}
posted:
last update: