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

C - Cell Inversion

問題

長さ $2N$ の B と W からなる文字列 $S$ が与えられる。この文字列に対して、以下の操作を $N$ 回行う。

まだ選んでいない 2 つの index を選ぶ( $l, r$ とする)。
$S[l, r]$ を全て反転させる。

最終的に全部 W になるような操作列の個数を求めよ。

制約

$1 \leq N \leq 10^5$

考察

まず $N$ 個のマッチングを決めてしまえば、最終的な文字列は選ぶ順番に依存しない。そこでマッチングを左から決めていくことを考える。

$S_1$ に着目すると、これは絶対に一度だけ反転される。よって $S_1$ が W である場合、答えは $0$ になる。 $S_1$ が B である場合は 1 とペアになる index があるが、これは後で決めることにする。

次に $S_2$ に着目すると、これの反転する回数は以下の 2 パターンがある。

1 のペアを 2 にする場合は 1 回。
2 と 3 以降のどれかをペアにする場合は 2 回。

このうち $S_2$ が W になるのはいずれか一方のみである。

これと同じことが任意の index で言える。つまり、 $S_i$ を見ている時点で右端を保留しているペアが $K$ 個ある場合、

保留中のペアのうちいずれか 1 つの右端を $i$ にする場合は $K$ 回。
- どれと $i$ をペアにするかが $K$ 通りある。
- $K$ は 1 減る。
$i$ をペアの左端にする場合は $K + 1$ 回。
$K$ は 1 増える。

このうち $S_i$ が W になるのはいずれか一方のみである。ただし $K = 0$ の場合前者は選べない、つまり条件を満たすマッチングはない。

これを先頭から繰り返せばマッチングの数が求まる。ただし最終的に $K \neq 0$ になったときは、これは invalid なマッチングなので答えは 0 になることに注意。

最後にマッチングをどの順に適用するか、つまり $N!$ を掛ければ答えとなる。

実装例

提出 #7126968 - 第一回日本最強プログラマー学生選手権-予選-

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


using namespace std;
using mint = ModInt<1000000007>;

int main() {
    int N;
    string S;
    cin >> N >> S;

    int K = 0;
    mint ans = 1;
    for (auto c : S) {
        if ((c == 'W') == (K % 2 == 0)) {
            // 保留中のどれかの右端にする
            ans *= K;
            if ((--K) < 0) break;
        } else {
            // iを左端にする　右端は保留
            ++K;
        }
    }

    if (K != 0) {
        // invalidなマッチング
        cout << 0 << endl;
        return 0;
    }

    // N!を掛けて出力
    for (int i = 1; i <= N; ++i) ans *= i;
    cout << ans << endl;
    return 0;
}