TopCoder SRM615 DIV1 HARD (950pt)
Problem Statement
各文字はR, G, B, W であるような $N$ 文字の文字列 $C$ が与えられる.
また,正整数 $M$ が与えられる.
WをR, G, Bのいずれかに置き換えることで,以下の条件1~2を満たすような文字列が何通りできるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.
条件2を満たすための必要十分条件は,(条件1を満たし,かつ)全ての位置に対して,
という条件をみたすこと.
なぜこれで良いかというと,GreedyにRとGのペアを作っていって,適当に $M$ 個の部分列に割り振ることを考えれば良い.
例えば,作るペアは最も左のRと最も左のGを選ぶ,を繰り返していき,割り振りは,最初のペアを1個目の部分列に,次のペアは2個目の部分列に,$K$ 個目のペアは $(K\ {\rm mod}\ M) + 1$ 個目の部分列に割り振る.
よって,状態として(現在の位置,$r-g$の値,現在使ったRの数)を取り,DPすれば良い.
計算時間量は $O(NM^2)$.
// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ll long long
#define MD 1000000007
class AlternativePiles {
public:
int count(string C, int M) {
int i, j, k, N;
ll res = 0;
static ll dp[51][51], nx[51][51];
N = C.size();
rep(i,M+1) rep(j,M) dp[i][j] = 0;
dp[0][0] = 1;
rep(k,N){
rep(i,M+1) rep(j,M) nx[i][j] = 0;
rep(i,M+1) rep(j,M) if(dp[i][j]){
if(C[k]=='W' || C[k]=='B'){
nx[i][j] += dp[i][j];
if(nx[i][j] >= MD) nx[i][j] -= MD;
}
if(C[k]=='W' || C[k]=='R'){
if(i+1 <= M){
nx[i+1][(j+1)%M] += dp[i][j];
if(nx[i+1][(j+1)%M] >= MD) nx[i+1][(j+1)%M] -= MD;
}
}
if(C[k]=='W' || C[k]=='G'){
if(i > 0){
nx[i-1][j%M] += dp[i][j];
if(nx[i-1][j%M] >= MD) nx[i-1][j%M] -= MD;
}
}
}
rep(i,M+1) rep(j,M) dp[i][j] = nx[i][j];
}
res = dp[0][0];
return res;
}
}
Current time: 2024年03月29日21時39分12秒
Last modified: 2014年04月05日18時50分57秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM615 SRM_Div1_Hard Dynamic_Programming
トップページに戻る
Logged in as: unknown user (not login)