まわりくどいことをしていそうだが人間向けかもしれない
問題
解法
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
ネタバレ避け
S を時計回りに円環にした U を考えます。
このとき、U で時計回りに A,B,C の順になっているものを取れることになります。
これは、A-B のペアを N 組作って、各ペアは U で B -> A (時計回り)の間にある C を使うことができる、と言い換えることができます。
次に、C を無視して A と B だけについて考えます。
A を ( , B を ) としたカッコ列 T を考えると、T の累積和の min (タイブレークは左優先)から始まるように rotate することで、valid なカッコ列にできます。
実は、S をその場所で rotate したあとの A の左から i 番目と B の左から i 番目をペアにするのが C の条件を考えた時に最適なことが示せます。
以下、そのように S を rotate したあとのことを考えます。
左から i 番目の A の位置を l_i , B の位置を r_i とします。
このとき、Hallの定理より、全ての l_j <= r_i となる 1 <= i <= j <= N について、( S で l_j から r_i の間にある C の個数 ) + j - i + 1 <= N が成り立ち、かつ A,B,C が N 個ずつであることが良い文字列であることと同値であることがわかります。
C の個数の累積和配列を rui として整理すると、l_j <= r_i や i <= j は外してよく、
lma = - rui[l_i] + i の max
rma = rui[r_i] - i の max
としたときに lma + rma < N という条件になります。
あとは、どこで rotate するか全探索してそれぞれ dp すればトータル O(N^6) で解けます。
提出
