問題リンク
問題概要
'(', ')', '[', ']'からなる文字列で、括弧が正しく対応しているものを「良い括弧列」と呼ぶ。
偶数\(N\)と、長さ\(N\)の整数列\(A,B\)が与えられる。
長さ\(N\)の良い括弧列\(s\)に対し、\(i\)文字目が'('または')'ならば\(A_i\)点、'['または']'ならば\(B_i\)点が入る。
合計得点の最大値を求めよ。
解法
一度に4種類の文字を考えるのは複雑なので、まず次の問題を考える。
aとbからなる\(N\)文字の文字列で、次の性質を満たすのはどのような文字列か。
- aに'('または')'、bに'['または']'を対応させて、良い括弧列にできる (これを性質(1)とする)
すぐにわかることとして、aとbの個数はともに偶数個であることが必要である。
次に、文字列が性質(1)を満たすとする。この時、括弧列にした時、連続する2文字で()もしくは[]になる部分があるので、文字列ではaaもしくはbbと同じ文字が連続する部分が存在し、さらにこの2文字を削除してもその文字列は良い括弧列にできる。よってこの操作を繰り返して全ての文字を削除できる。
逆に、この操作が行えない文字列はababab...かbababa...のように奇数番目と偶数番目でaとbが完全に分かれるパターンしかない。
「連続する2文字を削除する操作」では奇数番目と偶数番目を1つずつ消し、さらに残った文字に対しその文字が奇数番目か偶数番目かという性質は保たれるので、性質(1)を満たさない文字列では奇数番目のaと偶数番目のaの数は異なる(bも同じ)。
よって、文字列が性質(1)を満たすならば次を満たす。
- 奇数番目のaと偶数番目のaの個数が等しく、奇数番目のbと偶数番目のbの個数も等しい (これを性質(2)とする)。
逆に、文字列が性質(2)を満たすならば性質(1)を満たす。これは、性質(2)を満たす限り連続するaaかbbが存在し、それを削除した文字列も性質(2)を満たすので、文字の削除を続けて空文字列にすることができ、削除した2文字に括弧を対応させていけば良い括弧列が得られることからわかる。
よって、性質(2)が性質(1)の必要十分条件であることがわかった。
また、性質(2)はaについての条件を満たせば、自動的にbも条件を満たすこと、またaとbの個数がそれぞれ偶数になることも簡単にわかる。
上の考察より、元の問題は次の問題に帰着できる。
長さ\(N\)の整数列\(A\)と\(B\)が与えられる。
次の条件を満たすように\(1 \leq i \leq N\)に対し\(A_i\)と\(B_i\)のどちらかを選んだ時の合計の最大値を求めよ。
- 偶数番目で選んだA/Bと奇数番目で選んだA/Bの個数が等しい
提出
https://atcoder.jp/contests/agc048/submissions/17507718
感想
橙になった。
意識して思考過程を多めに書いてみた。
