ARC 036 C - 偶然ジェネレータ

問題

問題概要

省略

解法

ランダムウォークの表のようなものを考えて、+y方向に、(1-0の数)、-y方向に(0-1の数)として表を考える。そして、dp配列に、dp[i][j][k] := i番目まで見て、(1-0)の最大値がjで、(0-1)の最小値がkの時の場合の数 として、更新していく。これまでの遷移の中で、y座標の一番上と一番下の値をを持っておくのがポイントで難しかった。求めるものは、どのような部分列を考えても、0の個数と1の個数の差がK以下でなければならないので、答えは、j+k　<=　Kであるものの合計を求めればよい。 下の解説がとてもわかりやすかった。

en30-algorithm.hatenadiary.jp

ミス

難しいdpだった。。

コード

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;
const int mod = 1e9 + 7;
//dp[i][j][k] := i番目まで見て、
// (1-0)の最大値がjで、(0-1)の最小値がkの時の場合の数
ll dp[310][310][310];

int main(void){
    int N, K; cin >> N >> K;
    string s; cin >> s;
    dp[0][0][0] = 1;
    rep(i, N)rep(j, N + 1)rep(k, N + 1){
        if(dp[i][j][k] == 0) continue;

        if(s[i] == '1'){
            (dp[i + 1][j + 1][max(0, k - 1)] += dp[i][j][k]) %= mod;
        }else if(s[i] == '0'){
            (dp[i + 1][max(0, j - 1)][k + 1] += dp[i][j][k]) %= mod;
        }else{
            (dp[i + 1][j + 1][max(0, k - 1)] += dp[i][j][k]) %= mod;
            (dp[i + 1][max(0, j - 1)][k + 1] += dp[i][j][k]) %= mod;
        }
    }

    ll ans = 0;
    rep(i, N + 1)rep(j, N + 1){
        if(i + j <= K){//(1-0)の最大値と(0-1)の最大値の差が　K 以下であればよい。
            ans += dp[N][i][j];
            ans %= mod;
        }
    }

    printf("%lld\n", ans % mod);
    return 0;
}