原案者でした。(ABC 400 開催おめでとうございます！)

原案者の想定解は公式解説と同様に Alien DP でしたが、面白い別解があるので簡単に紹介します。

まず、公式解説と同様、今回の問題は次の問題に言い換えることができます。

\(N\) 個のケーキから \(2K\) 個のケーキを選ぶ。
さらに選んだ各ケーキについて \(X, Y, Z\) どの特徴量を選ぶかを決める。
\(X, Y, Z\) 全てについて選ばれた回数は偶数回である必要がある。
選んだ特徴量の値の総和を最大化せよ。

この問題は次のように状態を持つ DP で \(\mathrm{O}(NK)\) で解くことができます。(答えは \(dp[N][2K][0][0][0]\) です)

• \(dp[i][n][a][b][c]\) : \(i\) 番目のケーキまで見たときに \(n\) 個のケーキを選んでいて、\(X,Y,Z\) を選んだ回数の偶奇が \(a,b,c\) である時の最大値

この DP を上手いこと高速化しましょう。

最適解において選ぶケーキの集合が \(S\) だとします。数列 \(A=(A_1,A_2,\dots, A_N)\) を \(A_i = \lbrack i \in S \rbrack\) を満たす数列とします。(\(\lbrack \mathrm{cond} \rbrack\) は \(\mathrm{cond}\) が真の時 \(1\) 、偽の時 \(0\) を取る関数)

\(A\) はどのような列をしているでしょうか？テストケースによっては \((0,1,1,0,1,0,0,0,1,0,0)\) のようにランダムな見た目をした数列になるでしょう。あるいは \((0,0,0,0,0,0,0,1,1,1,1)\) のように偏った数列かもしれません。

まず、この \(A\) の偏りをなくすために、はじめにケーキの列、すなわち \((X_i,Y_i,Z_i)\) の列をランダムにシャッフルしましょう。
そうした後に \(A\) を生成すると、\(A\) は一様ランダムそうな \(01\) 列になる、すなわち \((0,0,0,0,0,0,0,1,1,1,1)\) のように偏った数列は生成されないことが直感的にわかります。

この事実を深掘りしましょう。長さ \(N\) の数列に \(1\) が \(2K\) 個含まれることから、直感的には次の事実が言えます。

• ケーキの列をランダムにシャッフルした後に \(A\) を先頭 \(i\) 個まで見ると \(1\) はだいたい \(\frac{2Ki}{N}\) 個含まれる。

もう少し定式化します。ある十分大きい定数 \(B\) を取ったときに次の事実が成り立ちます。

• ケーキの列をランダムにシャッフルした後に \(A\) を先頭 \(i\) 個まで見たときの \(1\) の個数は高確率で \(\frac{2Ki}{N} - B\) 個以上 \(\frac{2Ki}{N} + B\) 個以下である。

正当性の議論は抜きにしてこの事実を認めてしまうと、なんと先の DP の計算量を削減することができます（！）DP の定義は

• \(dp[i][n][a][b][c]\) : \(i\) 番目のケーキまで見たときに \(n\) 個のケーキを選んでいて、\(X,Y,Z\) を選んだ回数の偶奇が \(a,b,c\) である時の最大値

でしたが、\(i\) を固定したときに \(n\) としてみるべき範囲は \(\frac{2Ki}{N} - B\) 以上 \(\frac{2Ki}{N} + B\) 以下です。よってその範囲だけ見て DP の遷移を行うだけで計算量が \(\mathrm{O}(BN)\) に落ちているというわけです。

さて、あとは正当性の議論、すなわち \(B\) をどのように取ったときに高確率で DP が成立するか、という話になります。確率的な理論保証も含めた議論は maspy さんの記事 で詳らかに行われていて、これによると \(B\) を \(\Theta(\sqrt{N})\) 程度で取れば高確率で DP が成功することが証明できるとわかります。

• 今回の問題はマルチテストケースなので少し議論が複雑になる部分もありますが、全ケース \(B=500\) 程度に取れば正当性は示せると思います。

以上でこの問題を \(\mathrm{O}(N^{1.5})\) で解くことができました。(定数倍が重いので通すには高速な実装が必要になります。)

• 実装例