方針

盤面 \(B\) に対して、各マスから銀を \(1\) 回動かした先の値の最大値を並べた盤面を \(\operatorname{Max}(B)\)、最小値を並べた盤面を \(\operatorname{Min}(B)\) とします。Alice と Bob が \(1\) 回ずつ動かす \(2\) 手分の更新を \(F(B)=\operatorname{Max}(\operatorname{Min}(B))\) とおくと、\(N=2k\) のときの価値盤面は \(F^k(A)\)、\(N=2k+1\) のときの価値盤面は \(F^k(\operatorname{Max}(A))\) です。

ここで、実は以下のことが成り立ちます（証明は後述）。

\(K=\lfloor H/2\rfloor+1\) とすると、任意の盤面 \(B\) について \(F^{K+1}(B)=F^K(B)\) が成り立つ。

このことを認めると、\(F\) は高々 \(K\) 回まで計算すれば十分です。偶数回の移動については \(A,F(A),F^2(A),\ldots\) を、奇数回の移動については \(\operatorname{Max}(A),F(\operatorname{Max}(A)),F^2(\operatorname{Max}(A)),\ldots\) を順に計算します。各クエリについて \(k=\min(\lfloor N/2\rfloor,K)\) とすれば、\(N\) が偶数なら前者の \(k\) 番目、奇数なら後者の \(k\) 番目の盤面の \((X,Y)\) が答えです。

クエリをあらかじめ \(N\) の偶奇と \(k\) ごとに分類しておくことで、盤面を順に更新しながら対応するクエリに答えられます。

なお、この事実により、Alice・Bob それぞれについて残り手数ごとの価値盤面を \(1\) 手ずつ更新し、\(2\) 手前の状態と一致した時点で打ち切る DP でも解くことができます。

証明

任意の整数 \(a\) を固定し、各マスについて「値が \(a\) 以上であるか」だけを考えます。\(F^t(B)\) において値が \(a\) 以上であるマスの集合を \(S_t\)、マス \(v\) から銀が \(1\) 手で移動できるマスの集合を \(M(v)\) とします。\(\operatorname{Min}\) ではすべての移動先の値が \(a\) 以上である必要があり、その後の \(\operatorname{Max}\) ではそのような移動先を \(1\) つ選べばよいので、

\[ v\in S_{t+1}\iff M(u)\subseteq S_t\text{ となる }u\in M(v)\text{ が存在する} \]

が成り立ちます。以下では証明中のみ、行番号を \(0,1,\ldots,H-1\) とします。

\(S_t\) に新しく入るマス

\(t\ge1\) とします。第 \(r\) 行に \(S_{t+1}\setminus S_t\) に属するマスが存在するなら、第 \(r-2\) 行に \(S_t\setminus S_{t-1}\) に属するマスが存在することを示します。

\(v=(r,c)\in S_{t+1}\setminus S_t\) とします。\(v\in S_{t+1}\) なので、ある \(u\in M(v)\) について \(M(u)\subseteq S_t\) です。もし \(v\) から \(u\) への移動が斜め移動なら、その逆向きにも移動できるため \(v\in M(u)\subseteq S_t\) となり矛盾します。よって \(u=(r-1,c)\) です。また \(v\notin S_t\) なので \(M(u)\subseteq S_{t-1}\) ではなく、ある \(w\in M(u)\) が \(S_t\setminus S_{t-1}\) に属します。

\(u\) から移動できるマスは、第 \(r-2\) 行のマスと第 \(r\) 行の左右のマスです。もし \(w=(r,c\pm1)\) なら、\(w\) も \(S_t\setminus S_{t-1}\) に属するため、同じ議論から \(w\) を \(S_t\) に含めるために使われるマスは \((r-1,c\pm1)\) です。しかし、このマスへは \(v\) から斜め上に移動できるので、\(v\) もすでに \(S_t\) に含まれることになり矛盾します。したがって、\(w\) は第 \(r-2\) 行に存在します。

以上を繰り返すと、第 \(r\) 行に \(S_{t+1}\setminus S_t\) に属するマスが存在するなら、第 \(r-2t\) 行に \(S_1\setminus S_0\) に属するマスが存在します。第 \(0\) 行からの移動はすべて可逆な斜め移動なので、第 \(0\) 行ではこのような変化は起こりません。よって \(r-2t\ge1\) であり、特に \(S_{t+1}\setminus S_t\) が空でないなら \(t\le\lfloor(H-2)/2\rfloor\) です。

\(S_t\) から外れるマス

各 \(t\) について、\(Z_t=\{u\mid M(u)\cap S_t^c\neq\emptyset\}\) とします。\(Z_t\) は、\(1\) 手で \(S_t\) の外へ移動できるマスの集合です。先ほどの更新条件を否定すると、\(v\notin S_{t+1}\) であることと \(M(v)\subseteq Z_t\) であることは同値です。

また、\(Z_t\) も \(S_t\) と同じ更新則に従います。実際、\(u\in Z_{t+1}\) であることは、ある \(v\in M(u)\) が \(S_{t+1}\) に含まれないことと同値なので、

\[ u\in Z_{t+1}\iff M(v)\subseteq Z_t\text{ となる }v\in M(u)\text{ が存在する} \]

が成り立ちます。これは \(S_t\) の更新則と同じです。

ここで \(t\ge1\) とし、\(v\in S_t\setminus S_{t+1}\) とします。\(v\notin S_{t+1}\) なので \(M(v)\subseteq Z_t\) です。一方、\(v\in S_t\) なので \(M(v)\subseteq Z_{t-1}\) ではありません。したがって、ある \(w\in M(v)\) が \(Z_t\setminus Z_{t-1}\) に属します。つまり、\(S_t\) から \(S_{t+1}\) の間に集合から外れるマスが存在するなら、\(Z_{t-1}\) から \(Z_t\) の間には集合に新しく入るマスが存在します。

\(Z_t\) にも先ほど示した上界を適用できるため、\(t-1\le\lfloor(H-2)/2\rfloor\)、すなわち \(t\le\lfloor H/2\rfloor\) です。\(t=0\) についてもこの上界は自明に成り立ちます。よって、\(S_t\) から \(S_{t+1}\) への変化が起こり得るのは高々 \(t=\lfloor H/2\rfloor\) までです。

したがって \(K=\lfloor H/2\rfloor+1\) とすると \(S_{K+1}=S_K\) です。これは任意の整数 \(a\) について成り立つため、元の整数盤面についても \(F^{K+1}(B)=F^K(B)\) が成り立ちます。

計算量

\(\operatorname{Max}\) と \(\operatorname{Min}\) は、各マスについて高々 \(5\) 個の移動先を調べればよいため、それぞれ \(O(HW)\) で計算できます。\(F\) の適用回数は \(O(H)\) 回であり、各クエリは \(O(1)\) で答えられるので、時間計算量は \(O(H^2W+Q)\)、空間計算量は \(O(HW+Q)\) です。