公式解説と比べて計算量が \(O(\log C)\) 倍となる代わりに実装が非常に簡単となる解法を紹介します。

この問題は以下のように言い換えられます。

• 2つの括弧列 \(S_1\), \(S_2\)（正規括弧列とは限らない）とそれぞれの括弧に対応するコストの列 \(W_1\), \(W_2\) が与えられる。
• 括弧のペアが合計で\(K\) 個となるように \(S_1\), \(S_2\) それぞれから正規括弧列となる部分列を選ぶ。
• 選んだ括弧に対応するコストの合計の最小値を求めよ。

答えは \(K\) について下に凸なので（証明略）、ラグランジュ緩和を利用して以下のような問題を考えます（ラグランジュ緩和については、ABC218Hの解説などを参考にしてください）。

括弧のペアが合計で \(K\) 個であるという条件を無視する代わりに、括弧のペア 1 つにつきコストが \(\lambda\) 軽減されることにする。 コストの合計の最小値を求めよ。

括弧のペアに対するコストの軽減は、( に対応するコストから \(\lambda\) を引くことで実現できます。また、\((S_1, W_1)\), \((S_2,W_2)\) ごとに独立に解くことができます。

よって、次のような部分問題が解ければよいです。

括弧列 \(S\) とそれぞれの括弧に対応するコストの列 \(W\) が与えられる。

正規括弧列となる\(S\)の部分列を選んだときのコストの合計の最小値を求めよ。

まだペアになっていない ( のコストを優先度付きキュー（\(Q\) とする）で管理しながら、\(S\) を左から見ていきます。

• \(i=1,2,\cdots, |S|\) の順に \(S_i\)を見ていく。
  • \(S_i=\)(のとき
    • コスト \(W_i\) の ( を \(Q\) に push する
  • \(S_i=\))のとき
    • \(Q\) が空でないかつ \(Q\) の最小値と \(W_i\) の和が負なら、以下の操作を行う。
    • \(Q\) から最小値を pop して仮に対応させる。
    • \(S_i\) の直後にコスト \(-W_i\) の( を 仮想的に追加し、\(Q\) にpush する。この仮想的な ( が後ろの ) （\(r\) とする）と対応されることは、\(S_i\) と仮に対応付けされた ( が実際には \(r\) と対応付けられることを意味します。

以上のアルゴリズムによってコストの合計の最小値を求めることができます。

\(\lambda\) を二分探索することで、括弧のペアが \(K\) 個となるような部分列の選び方が得られるような \(\lambda\) を求めることができ、この \(\lambda\) におけるラグランジュ緩和後の問題の答えに \(K\lambda\) を足したものが元の問題の答えとなります。

ラグランジュ緩和の二分探索に \(O(\log C)\)、ラグランジュ緩和後の問題に \(O(N \log N)\) かかるので、時間計算量 \(O(N \log N \log C)\) でこの問題を解くことができました。

最後に類題を挙げておきます。これらの問題の解説等も参考にしてください。

• ABC250G（ラグランジュ緩和後の部分問題）
• ABC218H（ラグランジュ緩和）