WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM554 Div2 Hard "TheBrickTowerMediumDivTwo"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12164

色の付いたブロックでタワーを作る。
ブロックの色はC種類あり、それらは無制限に使うことが出来る。
タワーは各高さごとに2*2のブロックを使用する。

タワーを作るにあたってルールは以下の通り

  • 隣同士のブロックが同じ色の場所は多くてもK箇所とする。
 (2つのブロックがいずれかの面で接していたら隣同士とする)
  • タワーの高さは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;
        
    }
};