みんなのプロコン 2019 F - Pass (黄色, 900 点)

21:01 発の磐越西線 (会津若松 -> 郡山) に乗りながらのコンテスト参戦だった。

元々コンテスト出ないで問題だけ読んで考察だけ楽しむつもりが、この F がスラッと解けたので思わず提出してしまった。この段階ではまだ電波状態が大丈夫だった...のと、やはり易しく感じたならみんなちゃんと通して来ることを見越せなかった...

問題へのリンク

問題概要

人がそれぞれ一列に並んでいて、それぞれ

• 赤いボールを 2 個もつ
• 赤いボールと青いボールを 1 個ずつもつ
• 青いボールを 2 個もつ

のいずれかである。空の列に対して、 回以下の操作を行う。

• 先頭の人は持っているボールのうちの 1 個を選んで列の末尾に加える
• それ以外の人は持っているボールのうちの 1 個を選んで前の人に渡す
• ボールを持っていない人は何もしない

この操作によって 個のボールからなる列が作られる。そのような列の色の並びとして考えられる場合の数を 998244353 で割ったあまりを求めよ。

制約

• 

考えたこと

いわゆる「操作によってできるものを数え上げる」という問題。こういうのはまずは、「操作によってできるものがどういうものか」を考察することになる。

操作によって出来上がり得るものの同定

操作をそのままの言葉でとらえるとよくわからなくなるので、例えば の場合、

r r b r
r b b r

という風に 4 人がボールを持っているのに対して、最終的に列に push される順番に

1 4 3 8
9 2 7 5

のように書いてみることにする。そして、結構テキトーに数字を入れても案外実現できてしまうことがわかる。上の例だと、毎回各々の人が自分が持っているボールのうち番号が最小のものを前に渡すという風にすると、以下のようにちゃんと番号順に push できる。

1 4 3 6
8 2 7 5
↓
2 3 5 6
8 4 7
↓
3 4 6
8 5 7
↓
4 5 7
8 6
↓
5 6
8 7
↓
6 7
8
↓
7
8
↓
8
↓

操作が可能になるための、自明な必要条件を挙げてみる。まず

+ 1 は先頭の人が持ってなければならない
+ 2 は先頭か 2 人目が持ってなければならない
+ 3 は先頭から 3 人目までが持ってなければならない
+ ...
+ N は先頭から N 人目までが持ってなければならない
+ (N+1, ... は特に自明な必要条件はない)

というのがすぐにわかる。例えば i が i 人目が持っていた場合、それが毎ターン前に持って行かれることでギリギリ i 回目に push できることとなる。

そして、この条件を満たしながらいくつかの例を手で動かしていると、これが十分条件なのではないかと思えてくる。実際

---

どの人も毎ターン、小さい方のボールを前に渡す

---

とすることで、必ずできることを示せる。i ターン終了時点で

• i+1 は先頭がもち
• i+2 は先頭から 2 人目までが持ち
• i+3 は先頭から 3 人目までが持ち +...

となっていることを数学的帰納法によって示すことができる。まず i ターン終了時点で i+j が j-1 人目までが持っていたならば、次のターンで (i+1) + (j-1) が j-1 人目までが持つことになるのでよくて、i+j を j 人目が持っていたならば、j 人目のもう 1 つのボールが i+j より小さいことはありえない (帰納法の仮定に反する) ので、次のターンで前に渡すことになるので OK。

結局操作で出来上がるものは

以上の考察から、

---

個のボールの列は

• 先頭から 個までについては、 番目のボールは初期状態で 人目までが持っている必要がある
• 先頭から 個目以上については、初期状態で誰が持っていてもいい

---

ということがわかった。このことから、最初の 個のボールの並びを決めてしまえば、残りの並び替えは任意 (残りが赤 個、青 個だったら 通り) ということがわかる。

最初の 個でどんなら並びが何通できるのかを考えよう。

• dp[ i ][ r ] := i 回目の操作後に赤が r 個含まれる場合の数

として、最後に各 に対して

• dp[ i ][ r ] × (赤と青の残り個数に応じた場合の数)

を足しあげたものが答えになる。dp[ i ][ r ] は自然に組める。

• i + 1 人前までの赤の個数が r+1 以上ならば dp[ i + 1 ][ r + 1 ] += dp[ i ][ r ]
• i + 1 人目までの青の個数が i + 1 - r 以上ならば dp[ i + 1 ][ r ] += dp[ i ][ r ]

#include <iostream>
#include <string>
using namespace std;

const int MAX = 210000;
const int MOD = 998244353;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    long long b = mod, u = 1, v = 0;
    while (b) {
        long long t = a/b;
        a -= t*b; swap(a, b);
        u -= t*v; swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}



string S;
long long dp[5100][5100];
int sumr[5100];

int main() {
    COMinit();
    cin >> S;
    int N = S.size();

    sumr[0] = 0;
    for (int i = 0; i < N; ++i) {
        int num = 0;
        if (S[i] == '0') num += 2;
        else if (S[i] == '1') num += 1;
        sumr[i+1] = sumr[i] + num;
    }
    
    dp[0][0] = 1;
    for (int i = 0; i < N; ++i) {
        for (int r = 0; r <= i; ++r) {
            if (dp[i][r] == 0) continue;
            if (sumr[i+1] >= r + 1) {
                dp[i+1][r+1] += dp[i][r];
                dp[i+1][r+1] %= MOD;
            }
            if ((i+1)*2 - sumr[i+1] >= i + 1 - r) {
                dp[i+1][r] += dp[i][r];
                dp[i+1][r] %= MOD;
            }
        }
    }
    
    long long res = 0;
    for (int r = 0; r <= N; ++r) {
        res += dp[N][r] * COM(N, sumr[N] - r) % MOD;
            res %= MOD;
    }

    cout << res << endl;
}