問題概要

この問題では、"(", ")", "[", "]" からなる文字列を考える。

文字列 $x$ は，以下のいずれかの条件を満たすとき、良い括弧列と呼ぶ。

$x$ は空文字列である
ある良い括弧列 $s$ が存在し、"(", $s$ , ")" をこの順に連結すると $x$ が得られる
ある良い括弧列 $s$ が存在し、"[", $s$ , "]" をこの順に連結すると $x$ が得られる
ある空でない良い括弧列 $s$ および $t$ が存在し、 $s$ , $t$ をこの順に連結すると $x$ が得られる

偶数 $N$ と、長さ $N$ の整数列 $A$ および $B$ が与えられる。ここで、長さ $N$ の良い括弧列 $s$ に対して、そのスコアを次のように定める。

$s$ の $i$ 文字目のスコアは， $s_{i}$ が "(" または ")" ならば $A_{i}$ であり、 $s_{i}$ が "[" または "]" ならば $B_{i}$ である
文字列 $s$ のスコアは各文字についてのスコアの総和で決まる

長さ $N$ の良い括弧列のスコアとしてあり得る最大の値を求めよ。

制約

$2 \le N \le 10^{5}$
$N$ は偶数

考えたこと

カッコ列というと "(" なら +1、")" なら -1 といった変数を用意して色々やるイメージがある。そういう解法を考えるといかにも DP になりそうだけど、ちょっとその方向性では高速化できそうになかった。それにこれは AGC なので、「僕の知らない DP 高速化で解く」なんてことはなさそうだった。

なので、思い切って違う方向性で考えた。文字列 $S$ を "(" または ")" を A、"[" または "]" を B で置き換えると、

AABABAABAAABAA

のようになる。このような文字列としてあり得る必要十分条件をわかりやすく特徴づけようという方向性で考えることにした。そうすると存外わかりやすい特徴づけが得られた。

A-B 列の特徴づけ

まずカッコ列において、"(" と ")" とが対応するとき、その index の偶奇はかならず異なることに注意する。よって、次の必要条件が直ちに言える。

"A" の個数が偶数個
"A" となる index のうち、偶数であるものと奇数であるものの個数が等しい

たとえば ABAB は絶対に作れない。なぜなら A の index が (0, 2) となっていて、偶数が 2 個、奇数が 0 個となっていて等しくないからだ。なお、上の 2 条件を満たせば自動的に "B" についても同様の条件が満たされることに注意しよう。

さて、これは実は十分条件にもなっている！！！僕はちゃんと証明できてなかったのだけど editorial に明快な証明が載っている。

atcoder.jp

Greedy へ

以上でとてもよい特徴づけが得られたので最後の詰めに入る。index が偶数と奇数それぞれについて、

$B_{i} - A_{i}$

の値が大きい順に並べていく。簡単のため $A$ はすべて 0 としてよい。たとえば $B = (3, 6, -7, -9, 5, -2)$ であったときは、

i が偶数：5, 3, -7
i が奇数：6, -2, -9

というふうになる。こうしてできる $N/2$ 個の列それぞれについて、和が正なら "[]" 系統 (B) を、負なら "()" 系統 (A) を割り当てていけば OK。この例の場合、具体的には "[ [ ( ) ] ]" というふうになる。

コード

計算量は $O(N \log N)$ 。

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

int main() {
    int N;
    cin >> N;
    long long base = 0;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i], base += A[i];
    for (int i = 0; i < N; ++i) cin >> B[i], B[i] -= A[i];
    vector<long long> even, odd;
    for (int i = 0; i < N; ++i) {
        if (i % 2 == 0) even.push_back(B[i]);
        else odd.push_back(B[i]);
    }
    sort(even.begin(), even.end(), greater<long long>());
    sort(odd.begin(), odd.end(), greater<long long>());
    long long res = 0;
    for (int i = 0; i < even.size(); ++i) {
        if (even[i] + odd[i] > 0) res += even[i] + odd[i];
    }
    cout << res + base << endl;
}