SRM578 Div1 Medium "DeerInZooDivOne"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12543
訳
パステル君は一人でまっすぐな道を歩いていた。
彼は警戒している。
なぜならこの道にはオオカミがいることを耳にしていたからだ。
道はN個のマスで構成されている。
そのマスは順番に番号が0~N-1と振られている。
それぞれのマスには、オオカミが高々1匹徘徊している。
あなたはオオカミの位置にに関する情報をM個持っている。
その情報は、この区間は多くても2匹のオオカミが
徘徊しているというものである。
より正確には、あなたはleftとrightという2つの整数のリストを持っている。
その意味は、left[i]~right[i] ( 0 <= i <= M-1 )の範囲のマスには、
多くても2匹のオオカミがいる、というものである。
あなたは2つの文字列のリストL, Rが与えられる。
Lの要素を全て連結したものは、スペース区切りで、
left[0]~left[M-1]を表したものである。
同じくRの要素を全て連結したものは、スペース区切りで、
right[0]~right[M-1]を表したものである。
オオカミの配置が何通りあるかを返せ。
制約
1 <= N <= 300
1 <= M <= 50
考えた事
Div2 Hardをやったばっかの今なら解ける!!
0~N-1のマスを1~Nと番号を振りなおし、
dp[ 考えているマス ][ 最後に置いたマス ][ その前に置いたマス ]
= オオカミの配置の仕方のパターン数
・・というDPで解く
初期化
dp[ i ][ j ][ k ] = 0 ( 0 <= i, j, k <= N )
ただしdp[ 0 ][ 0 ][ 0 ]のみ 1(オオカミを全く配置しない場合)
考えているマスに、オオカミを配置しない場合
オオカミを配置しないのは必ず有効であるため、
dp[ i ][ j ][ k ] = dp[ i-1 ][ j ][ k ]となる
考えているマスに、オオカミを配置する場合
与えられた区間には2匹を超えるオオカミは配置できない。
そのため、dp[ cell ][ prev1 ][ prev2 ]として、
現在考えているcell, prev1, prev2について、
オオカミを配置できるかどうかを考える。
こんな場合は・・・
OK!!置いても区間内に2匹以内におさまる
こんな場合は・・・
NG・・・置いたら区間内が3匹になっちゃう・・
というわけで、prev2 <= left[ i ] かつ right[ i ] <= cell
となるような区間が存在した場合、
そのcell, prev1, prev2はNGとなる。
OKならば、
dp[ cell ][ cell ][ prev1 ] += dp[ cell ][ prev1 ][ prev2 ]
結果
dp[ N ][ j ][ k ] ( 0 <= j, k <= N )の総和となる。
計算量
cell, prev1, prev2でそれぞれで更新するのでO( N^3 )
それぞれで配置してもOKかNGかの判定を M 回使って行うので、
全体の計算量はO( N^3 * M ) ←ムリ
判定をO( N^2 * M )で前計算しておけば
全体をO( N^3 )に落とせる。
メモリ量
int[ 300 ][ 300 ][ 300 ] は100Mぐらい使うが、
SRMでの上限は64Mらしい!
DPの更新は1つ前のcellしか使わないため、
int[ 2 ][ 300 ][ 300 ]に落とせる。
ソースコード
static const int MOD = 1000000007; int dp[2][310][310]; bool ok[310][310]; // ok[i][j]にi - jに3個置けるか? class WolfInZooDivOne { public: int count(int N, vector <string> L, vector <string> R){ // 入力 int x; vector<int> l, r; stringstream ss_l( accumulate(L.begin(), L.end(), string()) ); while( ss_l >> x ){ l.push_back( x + 1 ); } stringstream ss_r( accumulate(R.begin(), R.end(), string()) ); while( ss_r >> x ){ r.push_back( x + 1 ); } int M = l.size(); // ok初期化 memset( ok, true, sizeof(ok) ); for( int i = 0; i <= N; i++ ){ for( int j = 0; j < i; j++ ){ for( int k = 0; k < M; k++ ){ if( l[k] <= j && i <= r[k] ){ ok[j][i] = false; } } } } // dp初期化 memset( dp, 0, sizeof(dp) ); dp[0][0][0] = 1; int c = 1; // 現在更新中のdpのindex for( int cell = 1; cell <= N; cell++ ){ int p = 1 - c; // 参考にするdpのindex for( int prev1 = 0; prev1 < cell; prev1++ ){ for( int prev2 = 0; prev2 < cell; prev2++ ){ // cellに置かないぞ dp[c][prev1][prev2] = dp[p][prev1][prev2]; // cellに置きたいぞ if( ok[prev2][cell] ){ // cellに置くぞ dp[c][cell][prev1] += dp[p][prev1][prev2]; dp[c][cell][prev1] %= MOD; } } } c ^= 1; } // 集計 int res = 0; for( int prev1 = 0; prev1 <= N; prev1++ ){ for( int prev2 = 0; prev2 <= N; prev2++ ){ res += dp[1-c][prev1][prev2]; res %= MOD; } } return res; } };