Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-10-09SRM484 Div1

SRM484 Div1 550 PuyoPuyo

| 14:30 | SRM484 Div1 550 PuyoPuyo - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM484 Div1 550 PuyoPuyo - SRM diary(Sigmar) SRM484 Div1 550 PuyoPuyo - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→いかにもDP

→うーん・・・両端の状態を覚えながらぷよを追加していくとかかな

→・・・

→駄目だな・・・同じ色が長く連続する場合に同じパターンを複数回数えてしまう

→250のためほとんど考えることもできず終了


終了後

→rngさんの解説を見て解き方を理解した

→自分の考えと照らし合わせながら解釈すると以下のようなことだろうか

(L=4とする)


最初に考えた(解けない)方法


以下のような感じで両端の状態を覚える

 青青○○・・・○○赤赤

同じ色L個を両端にくっつける

 黄黄青青○○・・・○○赤赤黄黄

このようなL個のくっつけ方はL通りくらいあるので適当にDPする


しかし上記の方法だと以下のようなパターンで失敗する


以下に対して

 青青○○・・・○○青青

さらに青をL個くっつける

 青青青○○・・・○○青青青青青

しかしこのパターンは以下のように何通りもの方法で作成できる

  青青青○○・・・○○青 青青青青

 青 青青○○・・・○○青青 青青青

 青青 青○○・・・○○青青青 青青

従って同じものを何度も数えてしまう

なので両端の色と数を全部覚える必要があり計算量が膨大となる


そこで両端の色や数を覚えなくて良い方法を考える

ここでポイントとなるのが同じ色L個が2連続する上記のようなパターンでは、実は必ず両端のどちらかはL個以上同色が連続する

こと

そうすると、全消しできるパターン2つに必ず分解できる

 青青青○○・・・○○青 青青青青

こんな感じ


この考えを応用して、全ての解となるパターンを、これ以上分解できない全消しパターンの組み合わせで表現すると、同じ色L個

を2回以上連続して両端にくっつける必要はないということになる

例えば以下のような感じで分解する(○○・・○○は分解可能なものを含めた全消しパターン)

 青青○○・・・○○青青 赤赤赤赤 黄○○・・○○黄○○・・○○黄黄 黄黄黄黄


分解不可能な全消しパターンは、必ず両端に同じ色が現れる

両端の間は、また分解不可能な全消しパターンの組み合わせとなるので、再帰的な構造となる

ただし、全消しパターンの両端に囲まれた全消しパターンは、以下の制約を受ける

(囲んでいるほうの全消しパターンを上位、囲まれているほうを下位とする)

 ・各下位全消しパターン間のどこかに、上位の両端と同じ色のぷよがL-2個現れる

 ・下位全消しパターンの両端は、上位の両端と異なる色となる


上記に留意してメモ化再帰でコーディングすると以下のようになる。

#かなり考え方が難しいですね。

const int MOD=1000000007;
int memo[502][11][5];

class PuyoPuyo {
public:
	int L;

	int rec(int n, int r, int mul) {
		ll res=0;

		if(n==0) return 1;

		if(memo[n][r][mul]>=0) return memo[n][r][mul];

		for(int i=1; i<=n; i++) {
			for(int j=0; j<=r; j++) {
				ll t;
				if(i>1) t=(ll)rec(i-1, L-2, 3)%MOD;//下位全消しパターンの数え上げ
				else t=1;
				res+=t*rec(n-i, j, mul)%MOD;//残りの上位全消しパターンの数え上げ
				res%=MOD;
			}
		}

		//最上位の全消しパターンは4色あるので4倍、最上位以外の全消しパターンは3色なので3倍する
		res=res*mul%MOD;
		memo[n][r][mul]=res;
		return res;
	}

	int theCount(int L, int N) {
		int res;
		this->L=L;
		int n=N/L;
		if(N%L) return 0;

		memset(memo, -1, sizeof(memo));
		res=rec(n, 0, 4);

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101009