【雑記】ABC312D

この記事はABC312のD問題について、僕が答えに辿り着くまでにあれこれ考えたことを記しておくメモです。有益では全くないので悪しからず。

問題はこちらになります。
https://atcoder.jp/contests/abc312/tasks/abc312_d

案1　Sの先頭から樹形図を考える

先頭から"("または")"を付け足していき、Sとしてありうるものを樹形図で列挙していこうという考えです。下の写真は入力例1のS=(???(?の場合です。

この方法の問題点は、Sの長さが大きくなるにつれて計算量も指数関数的に増加する点です。Sの長さが20とかなら問題ないかもしれませんが、今回は3000までありうるのでこの方法は不適切です。

案2　空文字列から出発して()の付け足し方で樹形図を考える

空文字→()→()()または(())というように、一個前の括弧列に対して()で包んであげるか()を横に置くかして一段階大きな括弧列を考えていくことで答えを計算できるのではないかという考えです。下の写真は入力例1のS=(???(?の場合です。

この方法の問題点は、案1と同様に計算量が大きすぎるという点です。また、最終的にSと同じ長さになった括弧列がSから導けるものであるかの判定が難しいという問題もあげられます。

案3　括弧列をより小さい括弧列に分割することを考える

括弧列はより小さな括弧列に分割できることがあるので、小さな括弧列についてのこの問題の答えから元の括弧列の答えを計算できるのではないかという考えです。例えば、入力例1のS=(???(?でいうと、答えは()()()と(())()の2パターンですが、この2つは、
()|()|()
(())|()
という区切り方ができます。なので、Sの長さが2や4のときの答えから今回の答えを導けるのではないかと考えていました。ただ、2つの括弧列をくっつけてSと同じ長さの括弧列を作ったとしても、それがSから導けるものなのかどうかという案2と同じ問題が発生してしまいます。

案4　Sの先頭から考えていき、"("が出たら前に一歩進む、")"が出たら後ろに一歩下がると考える

これが結果的に適切な考え方でした。以前も括弧列の問題に遭遇して、そのときにスタック構造を使ったのでそこから閃けた気がします。

分岐だけでなく合流することも許した樹形図というイメージを勝手に持っています。言い換えると樹形図の枝をとある条件(今回の場合だと、何文字目にどの位置にいるか)でくっつけているという感じがします。
案4だと案1～3で問題になっていた2点
①計算量の問題
②括弧列がSから導けるかどうかの問題
をどちらもクリアしてるんですね。①が解消できれば②はそこまで難しくなさそうなので、樹形図の枝のくっつけ方の切り口を見つけることが大事そうですね。どうすれば切り口を見つけられるかを言葉で表現したいんですけどまだぼくの力量が足りてないです。

最終的なコードは以下のようになり、これでACしました。動的計画法ですね。

#include <iostream>
#include <algorithm>

using namespace std;

int main(void){
    string S;
    cin >> S;
    int N = S.length();
    long long dp[N+1][N+1] = {};
    dp[0][0] = 1;
    for(int i=1;i<=N;i++){
        if(S[i-1]=='('){
            for(int j=1;j<=N;j++){
                dp[i][j] += dp[i-1][j-1];
                dp[i][j] %= 998244353;
            }
        }else if(S[i-1]==')'){
            for(int j=0;j<N;j++){
                dp[i][j] += dp[i-1][j+1];
                dp[i][j] %= 998244353;
            }
        }else if(S[i-1]=='?'){
            for(int j=1;j<=N;j++){
                dp[i][j] += dp[i-1][j-1];
                dp[i][j] %= 998244353;
            }
            for(int j=0;j<N;j++){
                dp[i][j] += dp[i-1][j+1];
                dp[i][j] %= 998244353;
            }
        }
    }
    cout << dp[N][0] << endl;
    return 0;
}

これでこの記事を終えます。ありがとうございました。