本解説では 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");
}