ABC 401-500/ABC407E - Most Valuable Parentheses - 競技プログラミング用 知識集積所

---

問題

ABC407E

必要知識

B以下レベルの内容は省略

• priority_queue（未作成）
• 貪欲法（アルゴリズム系）（未作成）

考え方

bit全探索（未作成）などを使っていては絶対に間に合わないので、工夫する必要がある。

まず、正しい括弧列の作り方について。
正しい括弧列は、

• 括弧を先頭から0個見たとき、'('が')'と同じ数ある
• 括弧を先頭から1個見たとき、'('が')'より多い
• 括弧を先頭から2個見たとき、'('が')'以上ある
• 括弧を先頭から3個見たとき、'('が')'より多い
• 括弧を先頭から4個見たとき、'('が')'以上ある
• 括弧を先頭から5個見たとき、'('が')'より多い
• （中略）
• 括弧を先頭から2*n-4個見たとき、'('が')'以上ある
• 括弧を先頭から2*n-3個見たとき、'('が')'より多い
• 括弧を先頭から2*n-2個見たとき、'('が')'以上ある
• 括弧を先頭から2*n-1個見たとき、'('が')'より多い
• 括弧を先頭から2*n個見たとき、'('が')'と同じ数ある

という形になっていればよい。
このうち、最後以外の偶数個の条件は、奇数個のときの条件が満たされたら自動的に満たされる。
したがって、

• 1番目はとりあえず'('にする
• 2番目3番目に')'を書き、いま')'になっているうち1つを'('に書き換える
• 4番目5番目に')'を書き、いま')'になっているうち1つを'('に書き換える
• （中略）
• 2*n-2番目2*n-1番目に')'を書き、いま')'になっているうち1つを'('に書き換える
• 2*n番目に')'を書く

という手順で（重複するのを見ないことにすれば）すべての括弧列を作ることができる。
よって、このなかで最大の和を作れる手順を見つければよい。

さて、次にスコアの決め方の表現について。
問題は')'に対応している場所を全て0に書き換えた状態での総和と言っているが、これはつまり、'('に対応する場所を全部足せと言っているだけである。

そこで、括弧列を作るときに'('に書き換える場所は、貪欲法（未作成）の考えに従って、今選べる一番大きいところを選んでいけば問題ない。
なぜなら、今最大でないものをあえて選択することに何も得する要素がないから。

ということで、今')'のまま残っている場所を管理するデータ構造を用意し、その中でそこの値が最大であるものを選び出す方法を考えればよい。
取り出したものを値しか使わない（つまり、位置を使わない）ことを考えると、priority_queue<int>でaの値だけ放り込んでいけば最大値を知るには十分であるとわかる。

解答例

解答例

注意点

別解