第二回 アルゴリズム実技検定 K - 括弧 解説

問題

問題文は本家サイトにあります：第二回 アルゴリズム実技検定 K - 括弧

問題概要

'(' と ')' からなる文字列 $S$ が与えられます。

まず、次の操作を0回以上行います。

操作： $S$ の $i$ 文字目を選ぶ。その文字が '(' の場合は ')' に変え、 ')' の場合は '(' に変える。この操作には、コスト $C_i$ がかかる。

続いて、次の操作を1回行います。

操作： $S$ から0か所以上選ぶ（連続していなくてもよいし、すべてを選んでもよい）。選んだ箇所にある文字を一度に全部削除する。残った文字をもとの順序でつなげる。なお、 $i$ 文字目を削除するには、コスト $D_i$ がかかる。

こうして、 $S$ を、括弧の対応が取れている文字列（定義はリンク先の問題文に記載）にするとき、合計コストの最小値を求めてください。

制約

$S$ の長さは1以上3000以下。
$1\leqq C_i, D_i \leqq 10^9$

解説

まず、1つ目の操作について考えます。 $i$ 文字目を変えた場合、再び変える必要はありません。同じ場所を2回以上変えるのはコストがかかって無駄です。また、 $i$ 文字目と $j$ 文字目の両方を変える場合、変える順番を入れ替えても、結果は同じです。つまり、文字列 $S$ を左から順番に見て、「そのまま」か「1回変える」かを決めていけばいいことがわかります。

次に、2つ目の操作について考えます。 $i$ 番目の文字を選んで削除する場合、1つ目の操作で文字を変える必要はありませんね。どうせ消すなら1つ目の操作ではそのままにしておいた方がコストはかかりません。

以上から、文字列に対する操作は、左から順番に見て、「そのまま」「変える」「削除する」のどれかを選んで実行していけばいいことがわかります。といっても、これでは処理のパターンが $3^N$ なので、もう少し考える必要があります。

続いて、「括弧の対応が取れている文字列」について考えてみましょう。これをもう少し扱いやすい表現にしたいですね。

すぐにわかるのは、こうした文字列は、「 '(' の数と ')' の数が同じ個数である」ということです。でないと、対応が取れていないことはすぐにわかります。

ただ、これだけではダメです。例えば、文字列の長さが6の場合でいうと、

())(()

のようなケースがダメです。 '(' も ')' も3個ずつありますが、3文字目の ')' や4文字目の '(' に対応するものがありません。このようなケースは除外しなくてはいけません。

何度か試行錯誤すると、次のようなことがわかります。左から順番に見ていって、各 ')' に対応する '(' が左側にあれば、2個セットにして消す、これを繰り返して何も残らなければOK、残るとダメ。先ほどの '())(()' だと1文字目と2文字目は消えますが、3文字目は消えることなくずっと残るのでダメです。

これをさらに管理しやすい形にします。 $j=0$ とし、左から順番に見て、 '(' なら1増やし、 ')' なら1減らすことにします。このとき、括弧の対応が取れていれば、それぞれの ')' に対応する '(' が左側にあるので、 $j$ はつねに0以上になり、そして、最後に $j=0$ になるはずです。 $j$ が途中で負になることがあれば、 ')' に対応する '(' が足りませんし、最後が $j\ne 0$ なら対応は取れていません。なので、このような $j$ の値に注目することにしましょう。

また、 $i$ 番目の文字までを見て、例えば '(' が ')' より3個多いとしましょう（つまり、先ほどの $j$ が $3$ ということ）。これは

(((
(((()
()((()(

などといったケースがありえますが、それより後の文字列で「 '(' が ')' より3個少ない」となっていれば、最終的に括弧の対応が取れることになります。ペアになるものを消せば、 '(((' が残ることからもわかるでしょう。つまり、 $i$ 番目の文字までを見たときに「 '(' が ')' より何文字多いか」だけを気にすればいいことがわかります。このことから、

$i$ 番目までの文字を見たときに「 '(' が ')' より $j$ 文字多い文字列」を作るのにかかる最小コスト

を管理すれば、動的計画法を用いて求めることができます。

さて、総まとめです。この括弧の対応と、1つ目・2つ目の操作との関係について、考えてみます。

i - 1 番目までの文字を見たとき、 '(' が ')' より j 個多い文字列があったとしましょう。

もし、 i 番目の文字が '(' だった場合、何もしなければ j は1増え、コストは変わりません。文字列を変えれば ')' に変わるので、 j は1減り、コストは C[i] だけ増えます。削除すれば、 j の値は増えも減りもしませんが、コストは D[i] だけ増えます。

このことから、次のように漸化式を更新していけばいいです。わかりづらいですが、 dp[i + 1] に i 文字目の結果を入れることにしています。

dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]); // do nothing
if (j > 0) { // change
  dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j] + C[i]);
}
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + D[i]); // delete

一方、 i 番目の文字が ')' だった場合、何もしなければ j は1減り、コストは変わりません。文字列を変えれば '(' に変わるので、 j は1増え、コストは C[i] だけ増えます。削除すれば、 j の値は増えも減りもしませんが、コストは D[i] だけ増えます。

このことから、次のように漸化式を更新していけばいいです。

if (j > 0) { // do nothing
  dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j]);
}
dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + C[i]); // change
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + D[i]); // delete

以上から、C++では、次のように書くことができます。コードの下に、コードの説明が続きます。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {

  ll N; cin >> N;
  string S; cin >> S;
  vector<ll> C(N); for (int i = 0; i < N; i++) cin >> C[i];
  vector<ll> D(N); for (int i = 0; i < N; i++) cin >> D[i];

  ll INF = 1e18;
  vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, INF));
  dp[0][0] = 0;
  for (int i = 0; i < N; i++) {
    if (S[i] == '(') {
      for (int j = 0; j < N; j++) {
        dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]); // do nothing
        if (j > 0) { // change
          dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j] + C[i]);
        }
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + D[i]); // delete
      }
    } else {
      for (int j = 0; j < N; j++) {
        if (j > 0) { // do nothing
          dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j]);
        }
        dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + C[i]); // change
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + D[i]); // delete
      }
    }
  }

  cout << dp[N][0];
  return 0;
}

i 文字目までを見て、 '(' が ')' より j 個多い文字列を作るのにかかる最小コストを順番に更新していき、その値が dp[i + 1][j] になるようにしています。初期値は、何もない状態で、括弧の数も 0 だから dp[0][0] = 0 とし、他は十分大きな値を入れておけばOKです。

dp[N][0] は、最後の文字列まで見て、括弧の対応が取れているものを作るのに必要な合計コストが入っているので、これが答えです。

これは一般に配るDPの書き方ですが、もらうDPで書き直すこともできます。 dp[i + 1][j] を更新するのは、 i - 1 文字目までの状態を基準として、 j + 1 から1減った場合、 j のまま変わらない場合、 j - 1 から1増えた場合のどれかです。これを踏まえて次のように書くこともできます。なお、配列は2次元にする必要もないので、1次元の配列を使いまわすようにしています。

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {

  ll N; cin >> N;
  string S; cin >> S;
  vector<ll> C(N); for (int i = 0; i < N; i++) cin >> C[i];
  vector<ll> D(N); for (int i = 0; i < N; i++) cin >> D[i];

  ll INF = 1e18;
  vector<ll> dp(N + 1, INF);
  dp[0] = 0;
  for (ll i = 0; i < N; i++) {
    vector<ll> dp2(N + 1, INF);
    if (S[i] == '(') {
      for (ll j = 0; j < N; j++) {
        if (j > 0) dp2[j] = min(dp2[j], dp[j - 1]); // do nothing
        dp2[j] = min(dp2[j], dp[j + 1] + C[i]); // change
        dp2[j] = min(dp2[j], dp[j] + D[i]); // delete
      }
    } else {
      for (ll j = 0; j < N; j++) {
        dp2[j] = min(dp2[j], dp[j + 1]); // do nothing
        if (j > 0) dp2[j] = min(dp2[j], dp[j - 1] + C[i]); // change
        dp2[j] = min(dp2[j], dp[j] + D[i]); // delete
      }
    }
    dp = dp2;
  }

  cout << dp[0] << '\\n';
  return 0;
}

dp には i - 1 文字目まで見た結果が入っていて、それをもとに i 文字目の更新を行って dp2 に入れる。というのを繰り返しています。各ステップの最後で、 dp2 の結果を dp に反映しています。最終的に、 dp[0] へ求めたい答えが格納されます。