TopCoder SRM615 DIV1 HARD - AlternativePiles

Source

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)$ で求める問題.

  1. RとGは同じ文字数で,それぞれ $M$ の倍数個だけ含まれる.$D$ を $($Rの文字数$/M)$ とする
  2. うまい手順で,$C$ から $M$ 回だけ,RGRG…RG という長さ $2D$ の 部分列を取り除くことができる.(結果 $C$ はBのみが残るか空文字列になる)

解法

条件2を満たすための必要十分条件は,(条件1を満たし,かつ)全ての位置に対して,

という条件をみたすこと.
なぜこれで良いかというと,GreedyにRとGのペアを作っていって,適当に $M$ 個の部分列に割り振ることを考えれば良い.
例えば,作るペアは最も左のRと最も左のGを選ぶ,を繰り返していき,割り振りは,最初のペアを1個目の部分列に,次のペアは2個目の部分列に,$K$ 個目のペアは $(K\ {\rm mod}\ M) + 1$ 個目の部分列に割り振る.
よって,状態として(現在の位置,$r-g$の値,現在使ったRの数)を取り,DPすれば良い.
計算時間量は $O(NM^2)$.

C++によるスパゲッティなソースコード

// #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: 2017年09月25日07時49分35秒
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)

ログイン: