けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 048 B - Bracket Score (青色, 700 点)

AtCoder AtCoder700点 AGC-B 青色diff パリティ 条件の言い換え Greedy 必要条件を列挙したら十分条件になる カッコ列 0と1の問題 最大スコア N個のペア値の問題 非自明な比較関数でソートする 探索順序を工夫して解く Greedy:よい順に取っていく 最適化問題

めちゃくちゃ面白かった

問題概要

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

文字列 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;
}