AtCoder ARC175 (2024-03-24 Sun)

ARC175 に参戦．問題 B にチャレンジするも NoSub……

• パフォーマンス：334
• レーティング：94 (+42)

問題Ｂ - Parenthesis Arrangement (400 点)

【問題ページ】 Difficulty: 924

問題の概要

長さ の"(", ")" からなる文字列が与えられ，コスト で隣接する文字を入れ替えるか，コスト で文字を反転させて正しい括弧列にするとき，必要なコストの総和の最小値を求める．

• 正しい括弧列とは，以下のいずれかの条件を満たす文字列．
  • 空文字列
  • ある正しい括弧列 が存在して，"(", , ")" をこの順に結合した文字列
  • ある空でない正しい括弧列 が存在して， をこの順に結合した文字列

制約条件

• 
• 

解き方

「正しい括弧列」という頻出？テーマ． "(" と ")" の個数が等しく，"(" を ，")" を として得られる数列の累積和の最小値が であるとき「正しい括弧列」となる．

コンテスト中にこれらの条件には気づいていたが，各操作でどれを入れ替える or 反転させるべきかがわからず，結局 AC は取れず． もう少しだったのにもったいない．

以下，コンテスト終了後に解説を見ながら組んだ AC コード (Python)．

n, a, b = map(int, input().split())
a = min(a, 2 * b)
s = list(input())
l = s.count("(")
r = 2 * n - l
d = l - r
rslt = 0
if l > r:
  for i in range(2*n-1, -1, -1):
    if s[i] == "(" and d:
      s[i] = ")"
      rslt += b
      d -= 2
else:
  for i in range(2*n):
    if s[i] == ")" and d:
      s[i] = "("
      rslt += b
      d += 2

cum, mn = 0, 0
for i in range(2*n):
  if s[i] == "(":
    cum += 1
  else:
    cum -= 1
  mn = min(mn, cum)
rslt += ((1 - mn) // 2) * a
print(rslt)

次回の ARC では少なくとも１問は AC を取る．

---

Best regards, e271828.