まず、Grundy 数を理解している方は Grundy 数を利用した解法がすぐに思いつくと思います。すなわち、連続する \(n\) 個の整数のみ存在する状態の Grundy 数を \(g_n\) として、\(g_1, g_2, \dots, g_n\) をすべて計算すればこの問題を解くことができます。しかし、この解法は愚直にやると \(\mathrm{O}(N^2 (R - L))\) かかってしまうため、工夫無しに AC するのは少し難しいと考えられます。 (問題の性質を利用した何らかの高速化を行えばこの方針でも通すことができるでしょう。)

この問題は俗に 真似っこ戦略 と呼ばれる戦略を取り上げた問題です。例として次の場合を考えましょう。

\(1, 2, \dots, N\) および \(N+2, N+3, \dots, 2N+1\) が書かれた \(2N\) 枚のカードが盤上に置かれている。この状態からゲームをスタートする場合、あなたが取るべき戦略は？

上の例の場合、実は後攻が必勝です。具体的には、先攻側が \((x, y)\) を選んだ時に \((x+N+1, y)\) または \((x-(N+1), y)\) のうち合法な方を選ぶ、というのを繰り返し続ければ必ず勝つことができます。

このように、すべての相手の着手 \(A\) に対して、自分の着手\(A'\) を 1 対 1 対応させて、相手の着手に対して対応する着手を返し続けて勝利する戦略はゲームによっては有効です。このような戦略は俗に真似っこ戦略と呼ばれています。

この問題も真似っこ戦略を利用すれば大半のケースを解くことができます。すなわち、先攻を選んで初手でカードの列を等分すればよいです。これは \(N \bmod 2 = y \bmod 2\) を満たす \(y\) を選び、\(y\) の値に応じて適切に \(x\) を選べば達成できます。

真似っこ戦略が適用できないのは \(L = R\) かつ \(N \bmod 2 \neq L \bmod 2\) の場合です。この場合は先述した Grundy 数を調べる方針で \(\mathrm{O}(N^2)\) で解くことができます。