ABC407 Eをdpで解く

ABC407 E - Most Valuable Parentheses

私自身はこの問題をコンテスト中に通すことはできなかったのですが、コンテスト中にdpで解く解法を考察したのでその解法を解説します。

注意
以下この問題のネタバレを含みます。

2乗のdp

まず、ベースとして$O(n^2)$のdpを考えます。このdpそのものは簡単ですし、考えた方も多いのではないでしょうか。
$dp[i][j]$を、$a[i]$までみて、)を$j$個使う構築で得られるスコアの最大値とします。
そうすると、

dp[i+1][j] = \max(dp[i][j]+a[i],\ dp[i][j-1])

のような遷移でdpテーブルを更新することができます。(初期値や$dp[i][j-1]$が定義されない場合については省略します）
実際には$j$は$i/2$を超えることはありませんので、存在する部分だけ作ればよいです。
このようにしてdpを計算し、$dp[2n][n]$を出力すればよいです。

入力例 1の最初のケースでは以下のようになります。

\begin{align}
dp[1] &: 400\\
dp[2] &: 900\ 400\\
dp[3] &: 1100\ 900\\
dp[4] &: 1200\ 1100\ 900\\
dp[5] &: 1500\ 1400\ 1200\\
dp[6] &: 2100\ 2000\ 1800\ 1200\\
\end{align}

sampleコード

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

using ll = long long;
const ll INF = 1LL << 60;

void solve() {
    int n;
    cin >> n;

    vector<int> a(2 * n);
    for(int i = 0; i < 2 * n; ++i) cin >> a[i];

    vector dp(2 * n + 1, vector(n + 1, -INF));
    dp[0][0] = 0;

    for(int i = 0; i < 2 * n; ++i) {
        for(int j = 0; j < (i + 1) / 2 + 1; ++j) {
            if(j)
                dp[i + 1][j] = max(dp[i][j] + a[i], dp[i][j - 1]);
            else
                dp[i + 1][j] = dp[i][j] + a[i];
        }
    }

    cout << dp[2 * n][n] << endl;
}

int main() {
    int testcase;
    cin >> testcase;
    for(int i = 0; i < testcase; i++) {
        solve();
    }
}

このdpで出力される値そのものは正しいですが、dpの構築に$O(n^2)$かかってしまい、残念ながらこの問題の制約では間に合いません。(ここまで考察して、あきらめて貪欲方針に切り替えた人が多いのかなと思います)

計算量の改善

上のdpを高速化して、計算量を改善します。
ちょっとアドホックな考察ですが、階差数列を取ってみましょう。

acc[i][j] = dp[i][j+1] - dp[i][j]

とすると、

\begin{align}
acc[1] &: \\
acc[2] &: -500\\
acc[3] &: -200\\
acc[4] &: -100\ -200\\
acc[5] &: -100\ -200\\
acc[6] &: -100\ -200\ -600\\
\end{align}

のようになります。ここで、この各要素はaの値の符号を変えたものになっていることがわかると思います。

実は、先ほどのdpの遷移について、階差数列$acc$は$-a[i]$をaccが降順になるように挿入したものになります。

この事実を言葉で証明するのはちょっと大変ので、実験してみるといいと思います。

先ほどの入力例 1の最初の入力の次の要素として、$a[7] = 400$が存在していたとしましょう。
このとき、$dp[7]$は、$j = 5$も作ることにすると、

\begin{align}
dp[6] &: 2100\ 2000\ 1800\ 1200\\
dp[7] &: 2500\ 2400\ 2200\ 1800\ 1200\\
\end{align}

となり、$acc$は

\begin{align}
acc[6] &: -100\ -200\ -600\\
acc[7] &: -100\ -200\ -400\ -600\\
\end{align}

となりますが、確かに-400を降順となる位置に挿入した結果となりました。

以上の考察から、計算量を改善することができます。
$dp[i]$を直接管理するのではなく、$dp[i][0]$と、$acc[i]$を管理することにします。
ここで、$dp[i][0]$は$a$の和を取るだけですし、$acc[i]$については$acc[i-1]$の降順となる位置に-a[i]を挿入すればよく、これはstd::multisetによって実現できます。(いちいち新たに構築する必要はなく、insertするだけでよいです)

また、それだけでは存在しない部分も作ってしますが、適宜最後の要素をeraseすればよいです。

以上のようにして、計算量$O(n\log n)$で解くことができました。

sampleコード

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

using ll = long long;
const ll INF = 1LL << 60;

void solve() {
    int n;
    cin >> n;

    vector<int> a(2 * n);
    for(int i = 0; i < 2 * n; ++i) cin >> a[i];

    multiset<ll> acc;
    ll dp_0 = 0;

    for(int i = 0; i < 2 * n; ++i) {
        dp_0 += a[i];
        acc.insert(-a[i]);
        if(i % 2 == 0) acc.erase(acc.begin());
    }

    for(auto e : acc) dp_0 += e;
    cout << dp_0 << endl;
}

int main() {
    int testcase;
    cin >> testcase;
    for(int i = 0; i < testcase; i++) {
        solve();
    }
}

最後に

割と強い人が、2乗から落ちなくて諦めたみたいなポストをしていたので解説を書いてみました。
あまり見ないテクですが、atcoderの問題でどこかで見たような気がします。(物理好きさんの解説だったような)
(2025/05/26 21:25 追記)
読者に教えてもらいました。この問題でした

本番で通したかったです...

以上です