AtCoder C - Cell Inversion

問題

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

atcoder.jp

リアルタイムで参加したのですが, B問題を無限にバグらせてしまい20分くらいしかかけられませんでした. コンテスト終了後に考察したがわからずでした

方針

今回注目するのは左右の関係です.ここでいう関係というのは同じ色か違う色かです. 例えば B Bや W W と続いていたら同じ色. B W や W Bの繋がりは違う色となります. どちらかを反転させた時に左右の関係いついてみてみます .

選んだ時の変化

太文字の B Wは最初別の色です. 左図のように, これら二つとも囲む際に左端になるように囲むと, 同じ色に変化します. (二つとも右端になるように選んでも同様に同じ色に変化する ).
左端と右端のように別の端として囲む場合には, 共に色は反転しますが, 異なる色という観点では変化していません.
二つの連続する文字が同じ場合は変化させてはいけないので , 異なる端として選ぶ ( 右端 & 左端 ) or (左端 & 右端 )
二つの連続する文字が異なる場合は変化させなければはいけないので , 同方向の端として選ぶ ( 右端 & 右端 ) or (左端 & 左端 )

この考えを元に文字列全体の左から順番に決めていきます. 文字の一番先頭の文字は必ず 左端となります .

左端か右端か

全ての文字が左端になるか右端になるかを決定することができます.

あとは計算の過程に移ります.
この問題の特徴としては, 囲む順番を逆にしても問題はです . 1 ~ ３番目を囲んだ後に 2 ~ 4番目を囲むのと , 2 ~ 4番目を囲んでから 1 ~ 3番目を囲むのは 結果は変わりません .(別の操作としてカウントはする)
なので一つ囲み方を決めてしまうと 順番の入れ替えでそれぞれ N の階乗通りの囲む方法が存在します.

どのような囲み方( 順番を考慮しない ) があるかを考えていきます .

右のラベルがついた位置に対して何通りの対応する左ラベルがあるかをカウントしていきます.

問題の入力例 2 で試します

回数

4文字目の右は3文字目までに左が3つあるので３通りです.
5文字目の右は4文字目までに左が3つありますが, 3つのうち1つは4文字目の右で使ってしまっているため,2通りとなります.
それぞれ何通りかが出れば掛け合わせて答えが出ます.

 3 * 2 * 2 * 1 = 12

これに囲む順番を考慮して並び替えを考えます . 今回囲む組みは4通りあるので

12 * 4 ! = 288

出力例に一致する答えを得ることができました.

コード

import java.util.Scanner;

class Main {
    static final long mod = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        sc.close();
        int array[] = new int[n * 2]; // 0は左1は右
        char tmp = s.charAt(0);
        if (s.charAt(0) == 'W') {
            System.out.println(0);
            return;
        }
        for (int i = 1; i < 2 * n; i++) {
            char c = s.charAt(i);
            if (tmp == c) {
                array[i] = 1 - array[i - 1];
            } else {
                array[i] = array[i - 1];
            }
            tmp = c;
        }
        long ans = 1;
        long left = 0;
        for (int i = 0; i < 2 * n; i++) {
            if (array[i] == 0) {
                left++;
            } else {
                ans *= left;
                ans %= mod;
                left--;
                if (left < 0) {
                    System.out.println(0);
                    return;
                }
            }
        }
        long fact[] = new long[n + 100];
        fact[0] = 1;
        fact[1] = 1;
        fact[2] = 2;
        for (int i = 3; i < n + 3; i++) {
            fact[i] = i * fact[i - 1];
            fact[i] %= mod;
        }
        ans *= fact[n];
        ans %= mod;
        if (left == 0) {
            System.out.println(ans);
        } else {
            System.out.println(0);
        }

    }
}

感想

区間反転問題, ごく稀に出題されるのかな, 覚えておきたい!