この解説の内容は、ユーザ解説と本質的に同じものです。正当性についてはリンク先と同様に証明できます。

この問題は、最終的に\(s_i=\)(となるすべての\(i\)についての\(A_i\)の和を最大化することが目的です。そこで、次の方法が考えられます。

\(A_i\)の降順に、\(s_i=\)(としても残りの文字を適切に決めることで最終的に正しい括弧列を構築できるなら\(s_i=\)(とし、スコアに\(A_i\)を加算する。

この方針は正しく、適切に実装することで問題を解くことができます。

\(s_i=\)(とできるかの判定方法

長さ\(2N\)の文字列のうちいくつかは既に(であることが分かっている時、残りの文字を適切に決めることで正しい括弧列を作ることができるかどうかの判定には、複数の方法が考えられます。ここでは、次の正しい括弧列の性質を利用した方法を示します。

• \(1 \le i \le 2N \) において、\(s_{i...2N} \)のうち(は\( \lfloor\frac{2N - i +1}{2} \rfloor\)個以下

この条件を用いるために、\(B_i = \) ( \(s_{i...2N}\)の未確定位置に配置できる最大の(の数)となる長さ\(2N\)の整数列\(B\)を定義します。条件より、\(B\)の初期値は\(B_i = \lfloor\frac{2N - i +1}{2} \rfloor(1 \le i \le 2N)\)となります。

整数列\(B\)を用いて、まだ確定していない文字\(s_i\)を(とできるかは次のように判定できます。

\[ B_{j} > 0 (1≤j≤i) \Leftrightarrow \min_{1≤j≤i}B_{j} > 0 \]

未確定の文字\(s_i\)を(と確定した時は、次のように\(B\)を更新します。

\[B_{j} \leftarrow B_{j} - 1(1≤j≤i) \]

よって、区間加算と区間最小値取得が高速に行えるデータ構造を用いることで問題を解くことができます。実装例ではACLのLazy Segtreeを利用しています。時間計算量は\(O(N \log N) \)です。

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

int op(int l, int r) { return min(l, r); }
int e() { return numeric_limits<int>::max(); }
int mapping(int l, int r) { return l + r; }
int composition(int l, int r) { return l + r; }
int id() { return 0; }

int main() {
	int t; cin >> t;
	while (t--) {
		int N; cin >> N;
		vector<pair<int, int>> A(2*N); //Aの値と元の位置のペア
		for (int i=0; i<2*N; ++i) {
			cin >> A[i].first;
			A[i].second = i;
		}
		ranges::sort(A, greater<>()); //Aを値の降順にソート

		vector<int> B_init(2*N);
		for (int i=0; i<2*N; ++i) B_init[i] = (2*N-i)/2; //Bの初期値を設定
		atcoder::lazy_segtree<int, op, e, int, mapping, composition, id> B(B_init); //区間加算,区間min取得の遅延セグメント木

		long long ans = 0;
		for (int i=0; i<2*N; ++i) {
			if (B.prod(0, A[i].second+1) <= 0) continue;
			ans += A[i].first;
			B.apply(0, A[i].second+1, -1); //Bの更新
		}
		cout << ans << "\n";
	}
}