SRM554 Div2 Hard "TheBrickTowerMediumDivTwo"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12164
訳
色の付いたブロックでタワーを作る。
ブロックの色はC種類あり、それらは無制限に使うことが出来る。
タワーは各高さごとに2*2のブロックを使用する。
タワーを作るにあたってルールは以下の通り
- 隣同士のブロックが同じ色の場所は多くてもK箇所とする。
- タワーの高さは1からHとする。
C, K, Hが与えられた時のタワーの作り方は何通りあるかを返せ。
制約
1 <= C <= 4
0 <= K <= 7
1 <= H <= 47
考えた事
dp[H][K][Cs] := 高さHで今までK箇所に同じ色のブロックが隣同士になっていて、
高さHの4つのブロックの色がCsとなっていた時の、タワーの作り方の数
とする。
初期値はdp[1][K][Cs]でKとCsを回して作る。
dp[1][Csで同じ色が隣同士になっている数][Cs] = 1;
更新は
newCs = 新たに置く4つのブロックの色
newK = K + CsとnewCsで隣同士が同じ色の数 + newCsで隣同士が同じ色の数
dp[H+1][newK][newCs] += dp[H][K][Cs]となる。
答えは
高さが1からHのdpに入ってる数値の総和となる。
事後
最大ケースで1.976sec...
bitDPみたく4つのブロックを1つの値にまとめたけど、
計算量が増えるだけでメリットなかたね。
あと変数名が紛らわしすぎて実装中混乱した。
ソースコード
const int MOD = 1234567891; int C, K, H; long long dp[55][10][260]; // dp[i][j][k] = 高さiでjだけペアを使った時に色をkで配置する時の場合の数 class TheBrickTowerHardDivTwo { public: // 4箇所の色を返す void getBrickColors( int bit, int* res ){ int div = C * C * C; for( int i = 3; i >= 0; i-- ){ res[i] = bit / div; bit %= div; div /= C; } } // この4つのブロックでの隣同士が同じ色の数を返す int getPair( int* cs ){ int res = 0; for( int i = 0; i < 4; i++ ){ int j = (i == 3 ? 0 : i + 1); if( cs[i] == cs[j] ) res++; } return res; } // この4*2のブロックでの隣同士が同じ色の数を返す int getPair( int* cul, int* next ){ int res = 0; for( int i = 0; i < 4; i++ ){ if( cul[i] == next[i] ) res++; } return res + getPair( next );; } int find(int _C, int _K, int _H){ C = _C; K = _K; H = _H; //dpリセット for( int i = 0; i <= 47; i++ ){ for( int j = 0; j <= 7; j++ ){ for( int k = 0; k < 4*4*4*4; k++ ){ dp[i][j][k] = 0; } } } //dp初期化 for( int i = 0; i < C*C*C*C; i++ ){ int c[4]; getBrickColors( i, c ); int j = getPair( c ); if( j > K ) continue; dp[1][j][i] = 1; } //dp更新 & 答えを足してく long long ans = 0; for( int i = 1; i <= H; i++ ){ for( int j = 0; j <= K; j++ ){ for( int k = 0; k < C * C * C * C; k++ ){ int c1[4]; getBrickColors( k, c1 ); if( dp[i][j][k] == 0 ) continue; ans += dp[i][j][k]; ans %= MOD; if( i == H ) continue; for( int k2 = 0; k2 < C * C * C * C; k2++ ){ int c2[4]; getBrickColors( k2, c2 ); int totalK = j + getPair( c1, c2 ); if( totalK > K ) continue; dp[i+1][totalK][k2] += dp[i][j][k]; dp[i+1][totalK][k2] %= MOD; } } } } return (int)ans; } };