問題概要

n人のすぬけ君が1列に並んでいて，両手にボールを持っている．両手のボールの色は青2つ，赤2つ，赤青1つずつのいずれかのである．

以下の操作を2n回繰り返した際にできるボール色の列のパターン数を998244353で割った値を求める．

操作: n人のすぬけ君それぞれが，自分の持つ2つのボールのうち1つを1つ前のすぬけ君に渡す．ただし先頭のすぬけ君は高橋君にボールを渡す．高橋君はもらったボールを順番に並べてボールの列を作る．

解法概要

実は「列のi番目のボールは，前からi番目以内のすぬけ君が持っているボールならどれにでもなりうる」．これはすぬけ君の人数に対する帰納法で証明できる．すぬけ君が0人の時は明らか．すぬけ君が(k-1)人で成り立つと仮定した時，すぬけ君がk人の時は先頭のすぬけ君のボールのうち一方が1番目のボールになる．先頭のすぬけ君のもう片方のボールは(k-1)人のすぬけ君で作った列のうち2番目以降どこにでも挿入できる．よって，

$ dp_{n,r} $= n個ボールを並べていて，そのうち赤いボールはr個のときの並べ方の数

として，DPで計算できる．

DPの初期値は，$ dp_{0,0} = 1 $．0個のものを並べるやり方は1通りなので． DPの遷移は，先頭(i+1)人のすぬけ君が持つ赤いボールを並べきっていなければ $ dp_{n+1,r+1} += dp_{n,r} $，並べきってしまっていたら$ dp_{n+1,r+1} = 0 $．同様に，先頭 (i+1) 人のすぬけ君が持つ青いボールを並べきっていなければ$ dp_{n+1,r} += dp_{n,r} $，並べきってしまっていたら$ dp_{n+1,r} = 0 $．

(ちなみに最初はボールがrgbの3色あると誤読していたが，実は2色だった．)

ソースコード

#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

const ll MOD = 998244353LL;

ll dp[4001][4001];

int main() {
    string s;
    cin >> s;
    int n = s.length();

    dp[0][0] = 1LL;
    int red = 0, r = 0;
    for(int i=0;i<2*n;++i) {
        if(i < n) {
            r = 2 - int(s[i] - '0');
            red += r;
        }
        for(int j=0;j<=min(i,red);++j) {
            if(j < red) {
                dp[i+1][j+1] += dp[i][j];
            } else {
                dp[i+1][j+1] = 0;
            }
            dp[i+1][j+1] %= MOD;
            if(i-j < min(i+1,n)*2-red) {
                dp[i+1][j] += dp[i][j];
            } else {
                dp[i+1][j] = 0;
            }
            dp[i+1][j] %= MOD;
        }
    }

    cout << dp[2*n][red] << endl;
}

所感

最近基礎的なDPなら理解できるようになってる気がする．

NoiminのNoise

みんなのプロコン 2019 F - Pass

問題概要

解法概要

ソースコード

所感