WARush

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

SRM582 Div1 Medium "ColorfulBuilding"

問題

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

N個の高層ビルが左から右へと一直線に建っている。これらの建物は1~Nと番号が振られている。(ただし、左から右へと順番に番号が振られているとは限らない)あなたはどのように番号が振られているのか分かっていない。番号iのビルの高さはiである。なので、N個のビルの高さは1~Nの順列となっている。

それぞれのビルは、1つの色で塗られている。複数のビルが、同じ色で塗られている場合もある。あなたは、i番目のビルが塗られている色について分かっている。(その情報の詳細については後ほど詳しく説明する)

あなたはこれらのビル群の左側の遠い位置に立っている。この場所からはビルは部分的に見えてくる。なぜなら、低いビルが、それより高いビルよりも遠い位置に建っていれば、それは隠れて見えなくなってしまうからだ。正確には、ビルXは、それよりも前の(ビルXよりも左側の)ビルが全てビルXよりも低ければ、(上側一部分かもしれないが)見えることになる。

さらに、遠い位置から見ているため、あなたは同じ色の2つのビルを区別する事はできない。具体的には、同じ色のビルH1とH2があり、その間に違う色のビルが見えるように建っていなければ、その2つのビルは1つのビルとしてあなたには見える。3つ以上同じ色のビルが連なっていても1つのビルに見えてしまう。

あなたにはL個のビルが見えている。言い換えれば、あなたの立っているところからはそのビル群はL-1回色が変わって見えるということである。

あなたにはString[]の color1とcolor2とint Lが与えられる。color1を文字列連結したものをC1、color2を文字列連結したものをC2とする。これはビルの色を表していて、i番目のビルの色はC1[i]+C2[i]である。ビルiとjにおいて、C1[i] == C1[j]、C2[i] == C2[j]であれば、2つのビルは同じ色である事を示す。

これらの情報より、ビルの建ち方が何パターンあるかを返せ。

制約

1 <= N <= 1296
1 <= L <= N



考えた事

dp[ 建てたビルの数 ][ 見えるビルの数 ][ 最後に建てたビルの高さ ] = 場合の数。。。だと計算量がヤバイからなぁ・・・。DPっぽいんだけど、ど~も上手い方法が分からん。


解法

コチラを参考にしました。m(_ _)m
SRM 582 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
writerとしても活躍されてるsnukeさんのブログですね。ありがとうございます。

やっぱりDP!!しかし・・・

しかし、番号N~1の順番でビルを置いていくのだという。ここですでに「ええっ!そ・・そんなDPのやり方があるのか!」である。


まず色は無視

色は無視して、ビルとビルの区別が必ずできるとしたときに、どのようにDPしていけばいいのか考える。dp[ 置いたビルの数 ][ 見えるビルの数 ] = 場合の数とDP式を立てると、この問題は解く事ができる。(正直これでもDiv2 Hardレベルな気がする)

初期化

dp[ 0 ][ 0 ] = 1 その他は0
0個ビルを置いて、見えるビルは0個なので、それは1パターンあるのである。

更新

・先頭(一番左)においた場合
この場合、見えるビルは1つ増える。よって、
dp[ i+1 ][ j+1 ] = dp[ i ][ j ]
となる。(+=としていないのは、これがdp[ i+1 ][ j+1 ]の最初の更新のため)

・それ以外
この場合、見えるビルは増えない。そして、置ける場所は既にビルが置かれている数分だけある。よって、
dp[ i+1 ][ j ] += dp[ i ][ j ] * i
となる。

結果

N個ビルを置いて、L見える場合なので
dp[ N ][ L ]が答えとなる。


色を考える

色を考えなければ、ビルを先頭に置くと必ず見えるビルは増える。だが色を考えると、同じ色が先頭(一番左)にあった場合、区別ができなくなって、見える数は増えなくなる。ここを考えなければならない。尚、ビルのインデックスはbase-0とします。

そこで、こんな情報があったらどうだろうか。
same_dp[ i ][ j ] = i個ビルを置いて、j個ビルが見えたときに、i番目のビルと同じ色のビルが先頭(一番左)だったときの場合の数。

same_dpを使ったdpの更新

・先頭(一番左)においた場合
この場合、先頭が同じ色のビルで無い場合のみ、見えるビルが一つ増える。よって、
dp[ i+1 ][ j+1 ] = dp[ i ][ j ] - same_dp[ i ][ j ]

先頭に置いても、same_dp[ i ][ j ]分は見える数が増えない。よって、
dp[ i+1 ][ j ] += same_dp[ i ][ j ]
となる。

・それ以外
dp[ i+1 ][ j ] = dp[ i ][ j ] * i

same_dpの更新

ここが一番むずかしい・・・


i番目のビルの、次の同じ色のビルのインデックスをns(next_same)とする。ビルiを先頭に置いてから、ビルnsまで、他のビルが先頭に一回も置かれない場合、nsのビルを置くときに、同じ色のビルが先頭にある事になる。他のビルを先頭に一回も置かないような置きかたは、( i+1 ) * ( i+2 ) * ... * ( ns-2 ) * ( ns-1 )だけある。

・先頭(一番左)に置いて、見える数が1つ増えた場合
(1 * 2 * 3 * ... * nをf[ n ]、1 * 2 * 3 * ... * nのmodの逆元をf_inv[ n ]とします)
増える場合は先に計算したdp[ i+1 ][ j+1 ]だけあります。よって、
same_dp[ ns ][ j+1 ] = dp[ i+1 ][ j+1 ] * f[ ns-1 ] * f_inv[ i ]

・先頭(一番左)に置いて、見える数が増えなかった場合
増えない場合はsame_dp[ i ][ j ]だけあります。よって。
same_dp[ ns ][ j ] += same_dp[ i ][ j ] * f[ ns-1 ] * f_inv[ i ]

・それ以外
先頭に置かなくてもsame_dp[ i ][ j ]だけ、同じ色が先頭に来ています。ビルiを先頭に置かない方法はiだけあるので、
same_dp[ ns ][ j ] += same_dp[ i ][ j ] * i * f[ ns-1 ] * f_inv[ i ]


事後

私男だけど、これを30分で解く男の人って・・・


ソースコード

const int MOD = 1000000009;

long long dp[1310][1310];
long long same_dp[1310][1310];
int next_same[1310];
long long f[1310]; 
long long f_inv[1310];

class ColorfulBuilding {
public:

    int count(vector <string> color1, vector <string> color2, int L){

        // f, f_inv初期化
        f[0] = f_inv[0] = 1;
        for( int i = 1; i <= 1300; i++ ){
            f[i] = f[i-1] * i % MOD;
            f_inv[i] = mod_inv( f[i] );
        }

        // 入力
        string C1;
        for( int i = 0; i < color1.size(); i++ ){
            C1 += color1[i];
        }
        string C2;
        for( int i = 0; i < color2.size(); i++ ){
            C2 += color2[i];
        }
        int N = C1.length();

        // 文字列反転
        reverce( C1 );
        reverce( C2 );

        // next_same初期化
        memset( next_same, -1, sizeof(next_same) );
        for( int i = 0; i < N; i++ ){
            for( int j = i + 1; j < N; j++ ){
                if( C1[i] == C1[j] && C2[i] == C2[j] ){
                    next_same[i] = j;
                    break;
                }
            }
        }

        // dp初期化
        memset( dp, 0, sizeof(dp) );
        dp[0][0] = 1;
        memset( same_dp, 0, sizeof(same_dp) );

        // dp更新
        for( int i = 0; i < N; i++ ){
            for( int j = 0; j <= L; j++ ){
                // 先頭に置いて、見えるのが1つ増えた
                dp[i+1][j+1] = ( dp[i][j] - same_dp[i][j] + MOD ) % MOD; // dpとsame_dpで逆転現象アリ!

                // 先頭に置いたが、見えるのが増えなかった
                mod_add( dp[i+1][j], same_dp[i][j] );

                // 先頭以外に置く
                mod_add( dp[i+1][j], dp[i][j] * i );

                if( next_same[i] != -1 ) {
                    int ns = next_same[i];

                    // 先頭に置いて、見えるのが1つ増えた
                    same_dp[ns][j+1] = dp[i+1][j+1] * f[ns-1] % MOD * f_inv[i] % MOD;

                    // 先頭に置いたが、見えるのが増えなかった
                    mod_add( same_dp[ns][j], same_dp[i][j] * f[ns-1] % MOD * f_inv[i] % MOD );

                    // 先頭以外に置く
                    mod_add( same_dp[ns][j], same_dp[i][j] * i % MOD * f[ns-1] % MOD * f_inv[i] % MOD );
                }
            }
        }

        return (int)dp[N][L];
    }

    long long mod_pow( long long a, long long b ){
        long long r = 1;
        while( b > 0 ){
            if( b & 1 ) r = r * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return r;
    }

    long long mod_inv( long long x ){
        return mod_pow( x, MOD - 2 );
    }

    void reverce( string& src ){
        int n = src.length();
        for( int i = 0; i < n / 2; i++ ){
            int j = n - i - 1;
            swap( src[i], src[j] );
        }
    }

    void mod_add( long long& target, long long val ){
        target += val;
        target %= MOD;
    }
};