AtCoder Grand Contest 054 D問題メモ

AtCoder Grand Contest 054

D - (ox)

いくつかの考察ステップが必要な難問。

• (,),o,x の4種の文字からなる文字列 $S$ が与えられる
• 隣り合う2文字をswapすることで、以下の条件を達成したい
• 条件
  • $S$ の全ての o を () で、x を )( で置き換える
  • この時、置換後の文字列は括弧の対応が取れている文字列である
• 最小の操作回数を求めよ
• $|S| \le 8000$
• $S$ は1組以上で同数の (,) を含む

まずアルゴリズム抜きにして、どうやったら最小値を達成できるのかを手で求めるのも結構難しい。

• o,x を置換する前に(,)だけを抽出した状態でも、括弧の対応がとれている必要がある
• x は1組以上の括弧に挟まれていないといけない

括弧の対応が取れた文字列とは、 「( を $+1$、) を $-1$ で置き換えて前から累積和を取っていったとき、 途中で一度も負にならない」という方法で検証できる。

各文字の時点での累積和を、その文字の「高さ」ということにする。

o,xを置き換えても、(,) が1個ずつに置き換わるので、前後で他の高さは変わらない。
よって、(,) だけを抽出したものも、対応が取れている必要がある。

また、o はどこにあってもそれによって正しい括弧列で無くなることはない。
一方、x は、)( で置き換えると高さが1減ってから増えるので、 最終状態では高さ $1$ 以上の位置に置かないといけない。

この2つさえ守られれば、括弧の対応が取れているといえる。

(例)  oo(xoox)oo(xx(ox)ox)oo

• ( は左に、) は右にのみ動かすとしてよい
• o,x 同士で操作する必要は無い
• 初期状態で高さ1以上の箇所は、両端の () を除きどの文字も動かす必要は無い

動かす目的は以下の2つに絞られる。

• ..)..(.. のように高さが負になっている部分を …()… のように解消する
• ..xoo().. のように外にある x を ..(xoo).. のように中に入れる

いずれも、( は左に、) は右に動かすことで達成できる。

また、xo を操作することに意味があるとすれば、 「xoo() を寄せていって oo(x) のように括弧の中に入れる」くらいだが、 その場合は( の方を動かして (xoo) としても操作回数は変わらない。

xxxxoo() のように中に入れたい x が複数ある場合は x を1個ずつ寄せていくより括弧を動かす方が必ずよい。

従って、xo,ox に対して操作する必要は無く、$S$ から括弧を除いた ox だけの並びは、 最初から最後まで変わらないとしてよい。

初期状態で高さ1以上の箇所は、動かす必要は無い。
（両端の (,) は x を含めるために広げるかも知れないが）

)o)o(x(x(o(x(x)x)x)o)o)x(x(
         ~~~~~~~~~
         ↓ 以下と答えは同じ
)o)o(x(x()o)o)x(x(

そのため、高さ1以上の部分の()の中身は無いものとして考えてよい。

これにより、最終状態は ( と ) が交互に出てくるという縛りができ、考察しやすくなる。

)o)o(x(x(o(x(x)x)x)o)o)x(x(  のままだと最終状態は

()oo(xx)(o(x(x)x)x)oo(x)(x)  みたいに交互にならないが、

)o)o(x(x()o)o)x(x(  高さ1以上を削除しておくと

()oo(xx)()oo(x)(x)  必ず交互になる

以降、$S$ は高さ1以上を削除済みとする。

o,x だけを取り出した並びは不変であることがわかった。
この文字列を OX文字列 ということにする。

最終状態において、OX文字列の間のどこに何番目の (,) を挟み込むか、を考える。

各括弧が元はどこにあった (,) かは一意に求まる。
(同士、)同士で、初期状態の並びを順番に当てはめていくとよい。

a b A B Cc d e D E
)o)o(x(x()o)o)x(x(  初期状態
↓
Aa  B  bCc  D dE e
()oo(xx)()oo(x)(x)  最終状態の一例
                    括弧の対応は一意に決まる

• $DP[i][j]=i$ 番目の (,) を、OX文字列の $j$ 番目の間隙までに挿入したときの最小コスト
  • $i$ 奇数番目は(、偶数番目は ) を挿入することになる

       j   0 1 2 3 4 5 6 7 8
OX文字列    o o x x o o x x

このDPで、答えが求められそう。
$j$ のように、OX文字列の間隙を表すindexを「間隙index」と呼ぶことにする。

この際、(,) が o,x を飛び越すコストと ),( を飛び越すコストを分けて、 DPでは o,x を飛び越すコストのみを考慮すると、見通しが良くなる。

a b A B Cc d e D E
)o)o(x(x()o)o)x(x(
↓
Aa  B  bCc  D dE e
()oo(xx)()oo(x)(x)

例えば上記の例で、Bの ( 括弧を初期状態から最終状態まで移動させるとき、 o,x は x 1個を飛び越せばよいというのは前後の間隙indexの差でわかるが、 ) はいくつ飛び越せばよいか。

( の初期状態での高さは0または負になっているが、 その絶対値だけ ) を飛び越すとすればよい。

この交換回数は、$S$ から (,) だけを取り出して対応の取れた括弧列とする交換回数と一致する。
（そもそも (,) だけの文字列を対応の取れたものにする交換回数の求め方がそれなので）

また、それぞれの (,) を最終状態でどこに位置させるかに依らず、一定である。

よって、(,) 同士の交換回数は別に求めておいて、 DPでは o,x との交換回数だけを考慮し、最後に合計すればよい。

• ( を元の間隙indexより右に持っていってはいけない
• ) を元の間隙indexより左に持っていってはいけない
• x は () に挟まれていないといけない

以上を満たすように遷移する。

$i$ が奇数の時。

基本的には、$DP[i][j]$ は、$j$ より左に $i-1$ 個目までの括弧を置いた場合の最小値に、 自身の交換回数 $F_i-j$ を加えたものとなる。
ここで $F_i=i$ 番目の括弧の初期間隙indexとする。

j=8
   2 3 4 5 6 7  8
...)o x o x o o ( :DP[i-1][2] ┬ この最小値に、
... o)x o x o o ( :DP[i-1][3] │ ( を j=8 まで持ってくるコスト
... o x)o x o o ( :DP[i-1][4] │ をあわせたものが DP[i][8]？？？
      :                       │
... o x o x o o)( :DP[i-1][8] ┘

基本的な考え方はそうなのだが、 ただし、x が括弧の外にならないよう考慮する必要がある。

そのためには、「最後にxが出てきた次からの最小値」とすればよい。

直前の閉じ括弧は、最後の x より右に無いといけない
→最小値として参照できるのは j=6,7,8 のみ

   2 3 4 5 6 7  8
... o x o x)o o ( :DP[i-1][6] ┬ この最小値に、
... o x o x o)o ( :DP[i-1][7] │ ( を j=8 まで持ってくるコストを
... o x o x o o)( :DP[i-1][8] ┘ あわせたものが DP[i][8]！！！

これで、DPを遷移できる。

が、$|S| \le 8000$ なので、DP配列は $O(|S|^2)$ 程度の大きさになりうる。 このそれぞれの遷移でさらに $O(|S|)$ 使っていたら間に合わないので、各 $DP[i][j]$ は $O(1)$ 程度で求める必要がある。

$DP[i][j]$ を $j=0$ から順番に求めるとき、累積的に最小値を更新していくことを考える。
現在の累積最小値 $cm$ を管理しておいて、

• OX文字列の $j$ 文字目が o なら、$cm \xleftarrow[\min]{} DP[i-1][j+1]$（最小値更新）
• OX文字列の $j$ 文字目が x なら、$cm = DP[i-1][j+1]$（上書き）

としていけば、$cm$ は条件に違反しない中で最適なコストになっており、ここに ( の移動距離 $F_i-j$ を合計したものが $DP[i][j]$ となる。

$j$ の動く範囲は、$F_{i-1}～F_i$ となる。

$i$ が偶数の時。

こちらは x を括弧内に入れることを考慮しなくていい分、いくらか簡単。
最初から全ての累積和を考えればよい。

0 1 2 3 4 5 6 7  8
(o o o x o x o o ) :DP[i-1][0] ┬ この最小値に、
 o(o o x o x o o ) :DP[i-1][1] │ ( を j=8 まで持ってくるコスト j-Fi を
 o o(o x o x o o ) :DP[i-1][2] │ たせばよい。
      :                        │
 o o o x o x o o() :DP[i-1][8] ┘

$j$ の動く範囲は、$F_i～|OX文字列|$ となる。

このようにして埋め終わったDPだが、最後の括弧)の位置として

• 右端にまだ x が残ってしまっていて、条件に違反するもの
• 右端の o を含めるためにわざわざ ) を移動させて不要なコストを増やしてしまっているもの

などがあり、どれが「条件を満たしつつ最適」なのか考慮する必要がある。

「OX文字列の一番右端に出てくる x」の位置を求め、 その位置より右に最後の ) があるパターンの最小値を求めればよい。

Python3

import os
import sys

import numpy as np


def reformat(s):
    # 高さ1以上を削除
    # 括弧だけを正しく並べるコストを計算
    # 'ox'だけをそのまま残した文字列に再編成
    # その並びの中で、i 番目の開き括弧・閉じ括弧がそれぞれ初期でどこにあったかを計算
    new_s = []
    balance = 0
    parentheses_cost = 0
    for c in s:
        if c == '(':
            if balance <= 0:
                new_s.append(c)
                parentheses_cost -= balance
            balance += 1
            continue

        if c == ')':
            balance -= 1
        if balance <= 0:
            new_s.append(c)

    if len(new_s) == 0:
        print(0)
        exit()

    opening_parentheses = []
    closing_parentheses = []
    ox_origin = []
    ox_i = 0
    for c in new_s:
        if c == '(':
            opening_parentheses.append(ox_i)
        elif c == ')':
            closing_parentheses.append(ox_i)
        else:
            ox_origin.append('xo'.index(c))
            ox_i += 1

    assert len(opening_parentheses) == len(closing_parentheses)

    return parentheses_cost, opening_parentheses, closing_parentheses, ox_origin


def solve(opening_parentheses, closing_parentheses, ox_origin):
    n = opening_parentheses.size * 2
    m = ox_origin.size
    INF = 1 << 60
    dp_from = np.full(m + 1, INF, np.int64)
    dp_to = np.full_like(dp_from, INF)
    dp_from[0] = 0
    l = 0

    for i in range(1, n + 1):
        is_opening = i % 2

        if is_opening:
            orig = opening_parentheses[i // 2]
            cur = l
            for j in range(l, orig + 1):
                dp_to[j] = orig - j + dp_from[cur]
                if j < m and ox_origin[j] == 0:
                    cur = j + 1
                    if dp_from[cur] == INF:
                        break
        else:
            orig = closing_parentheses[(i - 1) // 2]
            cur_min = dp_from[l:orig].min() if l < orig else INF
            for j in range(orig, m + 1):
                cur_min = min(cur_min, dp_from[j])
                dp_to[j] = cur_min + j - orig
            l = orig

        dp_from, dp_to = dp_to, dp_from
        dp_to.fill(INF)

    last_x = m
    while last_x > 0 and ox_origin[last_x - 1] == 1:
        last_x -= 1

    ox_cost = INF
    for j in range(l, m + 1):
        ox_cost = min(ox_cost, dp_from[j] + max(0, last_x - j))

    return ox_cost


SIGNATURE = '(i4[:],i4[:],i1[:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

s = input()
parentheses_cost, opening_parentheses, closing_parentheses, ox_origin = reformat(s)
opening_parentheses = np.array(opening_parentheses, np.int32)
closing_parentheses = np.array(closing_parentheses, np.int32)
ox_origin = np.array(ox_origin, np.int8)
ox_cost = solve(opening_parentheses, closing_parentheses, ox_origin)
print(parentheses_cost + ox_cost)