kmjp's blog

競技プログラミング参加記です

Google Code Jam 2015 Round 2 : D. Drum Decorator

本番思いつかなかったパターンがあったので、こりゃSmallも通るわけないよね。
https://code.google.com/codejam/contest/8234486/dashboard#s=p3

問題

ある円柱型のドラムの側面は、縦R行、横C列からなるグリッドに分けられている。
各マスには数値が書かれている。

「各マスには、隣接マス中に同じ数字が書かれたマスがその数字と同じだけある」
という条件を満たす数値のパターンが何通りあるか答えよ。
ただし、ドラムを円柱の軸に沿って回転させたとき同じパターンになるものは、同一と考える。

解法

Rは2以上、Cは3以上のため、各マスに書かれる数値は1~3の何れかである。

登場するパターンは、以下の何れかである。

  • 1. 3だけで構成される2行のパターン(横方向は1マス周期)
33333...
33333...
  • 2. 2だけで構成される1行のパターン(横方向は1マス周期)
2222....
  • 3. 1,2で構成される2行のパターン(横方向は3マス周期)
122122122...
122122122...
  • 4. 1,2で構成される2行のパターン(横方向は6マス周期)
112222112222112222...
222112222112222112...
  • 5. 1,2で構成される3行のパターン(横方向は4マス周期)
221222122212...
121212121212...
122212221222...

このパターンを元に、行ごとにDPでパターン数を列挙していく。
ただし以下の3点を状態として管理していく必要がある。

  • パターン2~5のを縦に並べると、1や2のマスが2,3個以上隣接してしまうので、これらは縦には並べられない。
    • よって、パターン1とパターン2~5は交互に並べるよう、直前のパターンがどちらか管理する必要がある。
  • パターン3~5はCがそれぞれの周期の倍数でなければ適用できない。
  • 回転して同じになるパターンは重複して数えないようにする。
    • これには、ここまでのパターンが何マス周期かを管理して処理する必要がある。
    • ここまでのパターンの周期をP、最後に追加しようとしているパターンの周期をQとすると、最後に追加したパターンにより全体の周期はLCM(P,Q)となり、また最後のパターンの置き方はGCD(P,Q)通りとなる。
int R,C;
ll mo=1000000007;
ll dp[105][2][25];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>R>>C;
	ZERO(dp);
	dp[0][0][1]=dp[0][1][1]=1;
	
	FOR(i,R) {
		FOR(j,25) {
			// 22222
			(dp[i+1][0][j] += dp[i][1][j]) %= mo;
			// 122122
			// 122122
			if(C%3==0) (dp[i+2][0][3*j/__gcd(3,j)] += __gcd(3,j)*dp[i][1][j]) %= mo;
			// 112222
			// 222112
			if(C%6==0) (dp[i+2][0][6*j/__gcd(6,j)] += __gcd(6,j)*dp[i][1][j]) %= mo;
			// 2122
			// 2121
			// 2221
			if(C%4==0) (dp[i+3][0][4*j/__gcd(4,j)] += __gcd(4,j)*dp[i][1][j]) %= mo;
			// 3333
			// 3333
			(dp[i+2][1][j] += dp[i][0][j])%=mo;
		}
	}
	
	 ll tot=0;
	 FOR(i,25) tot+=dp[R][0][i]+dp[R][1][i];
	
	_P("Case #%d: %d\n",_loop,tot%mo);
}

まとめ

面白い問題作るなぁ。

広告を非表示にする