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; } };