問題を簡単な設定から順に考えます。

case1: \(K = 1, N_1\):奇数 の場合

奇数長の数列についての関数 \(f\) を、

\[ f\left(B\right) = \begin{cases} B_1 & \left(|B| = 1\right) \\ \min\left(B_{\frac{|B|+1}{2}}, \max\left(B_{\frac{|B|+1}{2}-1}, B_{\frac{|B|+1}{2}+1}\right)\right) & (|B| \geq 3) \end{cases} \]

で定義します。答えは、 \(f\left(A_1\right)\) です。高橋君は

• \(A_{1, \frac{|A_1|+1}{2}-1} \geq A_{1, \frac{|A_1|+1}{2}+1}\) ならば、 \(A_1\) の最後の要素を削除する。
• そうでないならば、 \(A_1\) の最初の要素を削除する。

という戦略を取ると、ゲーム終了時に残る値を \(f(A_1)\) 以上に出来ることが数学的帰納法により分かります。一方、青木君は

• \(|A_1| \geq 4\) ならば、最後に相手が削除した方向と反対の方向から要素を削除する。
• \(|A_1| = 2\) ならば、自分の残したい要素を残す。

という戦略を取ると、ゲーム終了時に残る値を \(f(A_1)\) 以下に出来ることが数学的帰納法により分かります。

case2: \(N_i\): 奇数 \((i = 1, 2, \ldots K)\) の場合

答えは \(\sum_{i=1}^K f\left(A_i\right)\) です。高橋君は、

• これが高橋君の初めての操作であるか、直前の青木君の操作が偶数長の数列を奇数長にするものであった場合、長さが \(2\) 以上の数列 \(A_i\) を適当に選び、case1の高橋君の戦略と同様の操作を行う。(この戦略に従う限り、 \(A_i\) は奇数長であることが示せる)
• そうでないならば、最後に青木君が操作した数列 \(A_i\) について、case1の青木君の戦略と同様の操作を行う。(この戦略に従う限り、 \(A_i\) は偶数長であることが示せる)

という戦略を取ると、ゲーム終了時に残る値を \(\sum_{i=1}^K f\left(A_i\right)\) 以上に出来ることが数学的帰納法により分かります。一方、青木君は、

• 最後に高橋君が操作した数列 \(A_i\) について、case1の青木君の戦略と同様の操作を行う。(この戦略に従う限り、 \(A_i\) が偶数長であることが示せる)

という戦略を取ると、ゲーム終了時に残る値を \(\sum_{i=1}^K f\left(A_i\right)\) 以下に出来ることが数学的帰納法により分かります。

case3: 一般の場合

ここでは、 \(\sum_{i = 1}^K N_i - K\) が偶数の場合を考えます。

\(N_i\): 奇数 \((i = 1, 2, \ldots K)\) の場合の高橋君と青木君の戦略は、以下のように解釈することが出来ます。

• 奇数長の数列 \(A_i\) を操作することは得をしない。\(|A_i| \geq 5\) であれば、相手が反対の方向から要素を削除すれば中央の \(3\) 要素は不変に保たれる。 \(|A_i| = 3\) であれば、自分が先に \(A_i\) を操作してから相手が操作するより、相手が先に \(A_i\) を操作してから自分が操作した方が得をする。

以上の観察より、case2における高橋君と青木君の戦略は、以下のように一般化することが出来ます。

• 全ての数列が奇数長であれば、長さが \(2\) 以上の数列 \(A_i\) を適当に \(1\) つ選び、\(A_{i, \frac{|A_i|+1}{2}-1} , A_{i, \frac{|A_i|+1}{2}+1}\) のうち残したくない要素に近い方の端の要素を削除する。
• そうでないならば、各偶数長の数列 \(A_i\) について、 \(f\left(A[1:|A_i|-1]\right)\)と\(f\left(A[2:|A_i|]\right)\) の差分を計算し、最も利得の大きい操作を行う。

これが最適な戦略であることを、数学的帰納法により示します。偶数長の数列が存在しない場合はcase2と同様に示せます。偶数長の数列が存在する場合を考えます。 偶数長の数列を操作する場合、次の相手の操作以降は帰納法の仮定により利得の大きい操作から貪欲に行われ、奇数長の数列しか存在しない場合に帰着されます。帰着された状態を考えると、今の手番で最も利得の大きい操作を行うことが最適です。一方、奇数長の数列を操作する場合、相手にこの数列の反対の方向の要素を削除されると、総要素数が少なく、偶数長の数列は全て不変であり、奇数長の数列については元の状態より得をしていない状態に帰着されます。帰納法の仮定より得られるこの状態での最適戦略を考えると、この進行ははじめに偶数長の数列を操作した場合と比較して得をしないことが分かります。以上により、この戦略が最適であることが分かります。

以上より、各偶数長の数列 \(A_i\) について\(f\left(A[1:|A_i|-1]\right)\)と\(f\left(A[2:|A_i|]\right)\) の差分を計算し、高橋君と青木君が交互に貪欲に利得の大きい操作を行ったとして case2の場合に帰着させることによって、\(O\left(N\log N\right)\) の時間計算量でこの問題を解くことが出来ました。

\(\sum_{i = 1}^K N_i - K\) が奇数の場合も同様に考えることが出来ますが、奇数長の数列を操作する役割が高橋君から青木君へと移ることにより、 \(f\) の定義を変更する必要があることに注意してください。