AtCoder: 第一回日本最強プログラマー学生選手権-予選- C Cell Inversion (500)

問題はこちら

atcoder.jp

考え方

なんか自分で書いててもあまり納得感がないかもしれない... 記事を書いた後に自分がわかりやすかったものを参考として載せておきます。

misteer.hatenablog.com

Cで僕が考えたこと
・累積的な何かを考えるとよさそう
・[L, R]の反転は、[0, R]の反転と[0, L-1]の反転に分解できる
・つまりそれぞれの頂点xは[0, x]の反転として使う(Rにする)か[0,x-1]の反転として使う(Lにする)かのどちらか

— てんぷら (@tempura_cpp) August 24, 2019

step1 - 反転する操作の言い換え

まず、操作の順番を変えても答えは変わらないことに注意する。

任意の を選んでその区間を逆にする操作は、とに対してそれぞれ操作をすることと等価であることに注目する。

step2 - それぞれの文字が影響を及ぼす範囲を整理

つまり、番目に存在する文字は、以下のように考えることができる。

• として使った時は 自分を含めた 左側に影響を及ぼす。
• として使った時は 自分を含めない 左側に影響を及ぼす。
• に影響を及ぼすのは、それよりも右側にある文字だがこれの数は一定。

=> 以上より、番目よりも右側に存在する文字によって反転させられたあと自分の文字を変更できるのは、自分を として使うか、として使うかのどちらかのみ ということになる。

すべての要素は個あり、自分よりも右側のものに影響を受ける場合のみ考えると、終了時には以下のような状態になる。

// 0-indexで考える

if index % 2 == 0 then 色が反対に
else 色はそのまま

上記の操作を終了した時に、色を全て "W" にするためには以下のように振り分ける。

• "B" になっているものは として使う（自分を反転させるため）。
• "W" になっているものは として使う（自分を反転させないため）。

step3 - 組み合わせ計算

は自分よりも左側にある使われていない の数分だけペアになる候補がある。 よって累積のの数を数えておけばよく、疑似言語書くとこのようになる。

count = 1

for i in 2N:
  if is_right[i] == true:
    count *= left_count  
    left_count--

  else:
    left_count++

ただしよりも左側にまだペアになっていないがない時や、最終的にが余ってしまう時は答えは0なので、実装時はそこにも注意する。

最後に、操作順だけの場合の数があるので、をかけて出力する。

解答

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll mod = 1000000007;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
ll factorial(ll n) {
    ll ans = 1;
    while (n > 1) {
        ans *= n;
        ans %= mod;
        n--;
    }
    return ans;
}


int main() {
    ll n;
    cin >> n;
    string s;
    cin >> s;

    n *= 2;

    vector<bool> is_right(n);
    rep(i, n) {
        if (i % 2 == 0 && s[i] == 'W') is_right[i] = true;
        if (i % 2 == 1 && s[i] == 'B') is_right[i] = true;
    }
    ll ans = 1;
    ll left_sum = 0;
    rep(i, n) {
        if (is_right[i]) {
            if (left_sum == 0) {
                cout << 0 << '\n';
                return 0;
            }
            ans *= left_sum;
            ans %= mod;
            left_sum--;
        } else {
            left_sum++;
        }
    }
    if (left_sum > 0) cout << 0 << '\n';
    else cout << ans * factorial(n / 2) % mod << '\n';
    return 0;
}

Submission #7126826 - Japanese Student Championship 2019 Qualification