Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1596-408f1840
この記事にトラックバックする(FC2ブログユーザー)

SRM484 DIV1 MEDIUM - PuyoPuyo (この記事を編集する[管理者用])

Source

TopCoder SRM484 DIV1 MEDIUM (550pt)
Problem Statement
SRM484 DIV1 自分の参加記録

問題概要

1列のぷよぷよ.1個ずつぷよが落ちてくる.ぷよは全部で4色.L個以上並ぶと消える.
N個落ちてきたとき,ちょうど全部のぷよが消えた.
そのような落ち方のパターン数をmod 1000000007で求める問題.
Nは1000以下,Lは10以下.

解法

スタックを用意して,
 スタックの一番上の色のぷよが落ちてきたら,スタックから1個減らす
 それ以外の色のぷよが落ちてきたら,スタックにL-1個のぷよを追加する
と考えたとき,N個のぷよが落ちてきたとき,スタックが空になっているのと,全部のぷよが消えるのとは同値.
スタックはいろいろな状態があるけど,結局は,残りのぷよが落ちてくる数と,スタックに入っているぷよの総数だけでパターン数は決まる.
なので,状態数N^2のDPで解ける.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000000007

#define ll long long
ll dp[1200][1200];
int L;

ll solve(int rest,int st){
  ll res=0;

  if(dp[rest][st] >= 0) return dp[rest][st];
  if(rest < st) return dp[rest][st]=0;
  if(rest==0) return dp[rest][st]=1;

  if(st==0){
    res += 4*solve(rest-1,L-1);
  } else {
    res += 3*solve(rest-1,st+L-1);
    res +=   solve(rest-1,st-1);
  }

  return dp[rest][st]=res%M;
}

class PuyoPuyo {
public:
int theCount(int L_, int N) {
  int i,j;
  rep(i,1200) rep(j,1200) dp[i][j]=-1;
  L=L_;
  return solve(N,0);
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1596-408f1840
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。