問題へのリンク https://atcoder.jp/contests/abc312/tasks/abc312_d
問題概要
'('、')'、'?'の3つの文字からなる文字列Sが与えられる。 この時、'?'を'('または')'に置き換えて括弧列になるような置き換え方の個数を998244353で割った余りを出力せよ。
括弧列: すべての'('と')'を、'('、')'の順番のままペアを作れる文字列。例えば、(())は括弧列、 )(は括弧列ではない。
解説
動的計画法を用いる。
まず、括弧列の条件を考える。すると、次の2条件を満たすことが分かる。
- '('と')'が同数
- 文字列を左から見ていったとき、')'の数が'('を超えることはない。
1つ目の条件に関しては、'('と')'が同数で無ければ()のペアを作ることができない。2つ目は、')'の数が'('を超えると、超えた')'は左側に'('がないのでペアを作れない。
動的計画法の結果をメモする配列をdpとする。
dp[(左からi文字目まで見て)] ['('がj個] [')'がk個]]とすると、おおよそ計算回数が(Sの長さ)の3乗 (O(|S|)3、|S|はSの長さ)となり、Sが3000文字だった時にTLEになってしまいそうだ。
今回は、'('から')'を引いた数を管理することを考え、dp[(i文字目まで見て)] ['(' - ')'の数]とする。すると、最後の文字まで見て'(' - ')'が0なら、'('と')'が同数であるということになる。また、'(' - ')'がマイナスの値になる時は、')'の数が'('より大きくなり、条件2を満たさなくなっているので計算する必要がない。計算量もO(|S|^2)となり間に合う。
※今回は、S[i]は1始まりで考える。先頭の文字は0文字目ではなく1文字目とする。
dpの式は、配るdpで考えたとき、次の文字S[i+1]が'?'であれば'('の時と')'の時両方を選べる。S[i+1]が'('または')'の時はそれを選ぶしかない。
そのS[i+1]に基づいて、'('を選ぶとき、'(' - ')'の数は1増加し、')'を選ぶと'(' - ')'の数は1減少する。よって、次のようになる。
dp[i+1][j+1] = dp[i][j] (S[i+1] in ['(','?']) dp[i+1][j-1] = dp[i][j] (S[i+1] in [')','?'])
そして、最終的に出力すべき値はdp[N][0]である。
実装例(Python)
S = input() # Sの長さをNとする N = len(S) # 添字を1始まりにするため先頭に適当な文字を追加 S = "!" + S dp = [[0] * (N+1) for _ in range(N+1)] # 1文字も選ばずに、'(' - ')'=0になるように選ぶ方法は1通り dp[0][0] = 1 MOD = 998244353 for i in range(N): for j in range(N): #もしS[i+1]が'('または'?'なら if S[i+1] in ('(', '?'): # (を選ぶ dp[i+1][j+1] += dp[i][j] # 余りをとる dp[i+1][j+1] %= MOD #もしS[i+1]が')'または'?'なら if S[i+1] in (')', '?'): # )を選ぶ j-1<0の時は考えない if j-1<0: continue dp[i+1][j-1] += dp[i][j] # 余りをとる dp[i+1][j-1] %= MOD # N文字目まで見て'(' - ')'が0になる時が括弧列 print(dp[N][0])
