ABC312、D問題の初心者解説

0. はじめに

先日行われたABC312、D問題が比較的容易な動的計画法（DP）だったので、樹形図による解法を紹介します。

1. 問題と私のコード

以下、ACしたコード。

abc312_d.py

from collections import defaultdict

# 入力
s = list(input())
n = len(s)
mod = 998244353

# 樹形図の初期状態。0文字目について
if s[0]=="?" or s[0]=="(" :
  d=[defaultdict(int)]
  d[-1][1] = 1
# key = 閉じていない"("の個数
# val = 状態数
else:
# 先頭が")"なら計算終了
  print(0)
  exit()

# 樹形図的な状態の展開。1文字目以降
for i in range(1,n):
  d.append(defaultdict(int))
  s0 = s[i]
  for key,val in d[-2].items():
    if s0=="(":
      d[-1][key+1] += val%mod
    elif s0==")":
      if key-1>=0:
        d[-1][key-1] += val%mod
    else:
      d[-1][key+1] += val%mod
      if key-1>=0:
        d[-1][key-1] += val%mod
      
print(d[-1][0]%mod)    

2. 括弧列について

本問題は括弧列についての問題です。括弧列は頻出問題なので皆さんご存知かもしれませんが、典型的な解法の方針を一応書いておきます。

• "("を$+1$、")"を$-1$と数値で表現する。
• "("と")"が閉じる前提なら、負の値は許されない。

まず、"("を$+1$、")"を$-1$として変数で制御します。そして大部分（全て？）の問題では括弧が閉じる状態について回答を求めていますので、この場合、")"が先に来ることによって変数に負の値が格納されることは除外されるべきです。

括弧が閉じる前提からは文字列の長さは偶数であるなどの、問題を解くための条件が導かれます。

3. 解法説明

問題の概要は、「文字列が"("と")"と"?"から作られており、"?"には"("か")"が入る。閉じた括弧列は何通り存在するか？」、という数え上げ問題です。文字を一つずつ追って、最終的に閉じた括弧列になるような状態数を数え上げます。

このような問題は、もちろんDPに習熟した人たちは漸化式とDPテーブルで解くのでしょう。ただナップサック問題と同じように、この問題は樹形図的な状態の発展を追っていくことでシンプルに解くことができます。

樹形図的な発展と言っても小難しいことではなく、「$i-1$文字目までの状態が既知で、$i$文字目が"?"であるなら、"?"を"("とおくか")"とするかによって状態が分岐する」、というものです。動的計画法の問題を樹形図的に考えて辞書で実装することは、皆さんが紙に書いて確認するような状態の発展をプログラムで計算させよう、ということです。

では、先に紹介したコードを説明します。最初の入力部分は無視して、計算の出発点、0文字目による初期状態ですが、これは例え"?"であっても"("を選択するしかありません。なぜなら「閉じた括弧列」という条件から、最初に")"を選択するとそこで計算が終わってしましますので。

樹形図の各段階の状態の実装、この問題で言えば$i$文字目の状態の実装には辞書型を使います。この問題では、"("の個数を示す正の値を辞書のキーとします。そして"("の個数についての状態数を値とします。これは、コード中の説明コメントのとおりです。

次にfor文によって1文字目以降の状態の発展を追います。最初にそのステップでの状態を保存するために、リストに辞書を追加します。この辞書をdefaultdict(int)と初期化しておくと、余計な記述を省略できます。

そして状態の変化ですが、$i$文字目が"("なら（コード中のif s0=="(":）、キーを$+1$して、そのキーの値に元の状態の状態数を加算します。defaultdict(int)なら、ここがシンプルに書けます。「998244353」の余りをとることも忘れないように。

次に")"なら（コード中のelif s0==")":）、この場合はキーの値が1以上である事を確認しなければなりません。この1以上の値は、")"に対応する"("が1以上存在する事を意味します。もしキーの値が0の時に")"を選択すると、その場合は閉じた括弧列が破綻します。

最後に"?"の場合（コード中のelse:）、この時は"("も")"も選択できるので、今までの"("の場合と")"の場合を両方記述します。

このような選択を続けると最後の文字による状態変化が終わったときには、キーが正の値、つまり"("が多い状態も存在しますが、同時にキーが0、つまり"("と")"のバランスのとれた閉じた括弧列の状態も存在します。なので最後の答えの表示の際には、キーが0である「d[-1][0]」を選択します。

4. おわりに

実は今回のコードには、先に書いたような文字数の奇偶の判断が抜けているのですが、defaultdict(int)を使った事により、奇数個の文字列では「d[-1][0]=0」となりACします。丁寧に書いておくべきですね（汗）。

比較的容易なDP問題を樹形図と辞書で解くことについては、以下の記事を御覧ください。

• 動的計画法の辞書型データ構造による実装