Cell Inversion [第一回日本最強プログラマー学生選手権-予選- C]

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c

解説

https://atcoder.jp/contests/jsc2019-qual/submissions/7123399

何から手を付けていいかわからないかもしれない。
こういうときは、色々試していくしかないが、全探索対象を探してみる。
2Nマスに対して、N回操作を端点として選択するマスがかぶらないように操作をするということは、
各マスについて「先頭」か「末尾」をN個ずつ割り当てることになる。
この時、先頭を「(」、末尾を「)」とした時に正しいカッコ列である必要がある。

dp[i][open] := i番目まで全て白になっていて、ここまでカッコがopen個開いている組み合わせ
このdpでは解けないが、これによって、だいぶ解法に近づく。
遷移する時にちゃんとi+1番目が白になっていることを確認しながら、遷移を行う。
これをよくよく考えてみると、整合性を確認しながら、カッコを開くか閉じるか決めていくので、
各要素についてカッコが開くか閉じるかというのは一意に定まる。
よって、カッコを決める必要はなくなる。

ここまで来れば比較的簡単。
後問題になるのは、先頭と末尾が決まっているマスについて、N通りの組を作る組み合わせになる。
末尾の方を先頭から順番に見ていって、(そこまでに出ている先頭)-(そこまでに出ている末尾)の総積が組み合わせとなる。
最後にN!を書けると操作の組み合わせとなる。

int N; string S;
int A[201010];
#define open 1
#define close 2
//---------------------------------------------------------------------------------------------------
bool check(char c, int cnt) {
    if (cnt % 2 == 0 and c == 'W') return true;
    if (cnt % 2 == 1 and c == 'B') return true;
    return false;
}
//---------------------------------------------------------------------------------------------------
mint solve() {
    N *= 2;

    if(S[0] == 'W') return 0;

    A[0] = open;

    int cnt = 1;
    rep(i, 1, N) {
        if(check(S[i], cnt)) A[i] = close, cnt--;
        else A[i] = open, cnt++;

        if(cnt < 0) return 0;
    }

    if(cnt != 0) return 0;

    mint ans = 1;
    cnt = 0;
    rep(i, 0, N) {
        if (A[i] == open) cnt++;
        else {
            ans *= cnt;
            cnt--;
        }
    }

    N /= 2;
    rep(i, 1, N + 1) ans *= i;

    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    cout << solve() << endl;
}