数列操作

各数列を $X_i=2\sum_{k<i}A_k+A_i$ に変換する。位置 $i$ を削除すると、後ろの位置 $j$ について、距離が奇数なら前方の和が $A_i$ 減り、その要素は $2A_i$ 増える。偶数なら前方の和が $A_i$ 増え、要素は $2A_i$ 減る。よって変換値は不変で、対応する位置だけが削除される。 変換は可逆である。前方の和が $P$ なら次の要素は $X_i-2P$ で復元できる。したがって共通部分列を最長に残せばよい。LCS の長さを $L$ とすると答えは $N+M-2L$。 サブタスク 1 は実際の削除操作で到達状態を列挙する。状態数は高々 $2^N$ で、順序付き集合を使う実装の保守的時間上界は $O((2^N+2^M)(N+M)^3)$。全体解は LCS DP で時間 $O(NM)$、メモリ $O(M)$。 初期変換値の絶対値は $49\,995\,000$ 以下であり、以後もその部分列である。復元した各要素の絶対値は $(2\cdot5000-1)49\,995\,000<5\cdot10^{11}$ 以下なので、符号付き 64 ビット整数で十分。 Solution written by GPT6.1