SRM578 Div2 Hard "WolfInZooDivTwo"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12533
訳
パステル君は一人でまっすぐな道を歩いていた。
彼は警戒している。
なぜならこの道にはオオカミがいることを耳にしていたからだ。
道はN個のマスで構成されている。
そのマスは順番に番号が0~N-1と振られている。
それぞれのマスには、オオカミが高々1匹徘徊している。
あなたはオオカミの位置にに関する情報をM個持っている。
その情報は、この区間に少なくとも1匹のオオカミが
徘徊しているというものである。
より正確には、あなたはleftとrightという2つの整数のリストを持っている。
その意味は、left[i]~right[i] ( 0 <= i <= M-1 )の範囲のマスには、
少なくとも1匹のオオカミがいる、というものである。
あなたは2つの文字列のリストL, Rが与えられる。
Lの要素を全て連結したものは、スペース区切りで、
left[0]~left[M-1]を表したものである。
同じくRの要素を全て連結したものは、スペース区切りで、
right[0]~right[M-1]を表したものである。
オオカミの配置が何通りあるかを返せ。
制約
1 <= N <= 300
1 <= M <= 50
ACしているコードをカンニング
0~N-1マスを1~Nマスとしたときに、
dp[ cell ][ last ] = cellマスまでで、
最後にオオカミを配置したのがlastマスの時、
オオカミの配置の仕方が何通りあったか?
・・というDPで解く。
初期化
dp[ i ][ j ] = 0; ( 0 <= i, j <= N )
ただしdp[ 0 ][ 0 ] = 1(0マス目までに全くオオカミを配置しない)
cellマスにオオカミを配置する時
その配置は必ず有効であるため、
dp[ cell ][ cell ] =
dp[ cell-1 ][ 0 ] + dp[ cell-1 ][ 1 ] + ... + dp[ cell-1 ][ cell-1 ]
となる。
cellマスにオオカミを配置しない時
与えられた区間には、1匹以上配置しなければならないという制約があるので、
考えているcell, lastでcellマスに配置しなくて大丈夫なのかをまず判定する。
この場合は・・・
区間内に既にオオカミがいるんだから当然OK!!
この場合は・・・
OK!!だって次以降のマスに配置すればいいも~ん
この場合は・・・
NG・・・区間内に1匹は配置しなきゃね
この場合は・・・
これまたNG・・・そのcellには必ず配置しなきゃダメだね
という訳で、last < left[i] かつ right[i] <= cellな区間が存在した場合、
NGとなる。
OKなcell, lastでは
dp[ cell ][ last ] = dp[ cell-1 ][ last ]となり、
NGなcell, lastでは
dp[ cell ][ last ] = 0となる。
結果
全くオオカミを配置しない場合の数
+
1マス目までにオオカミを配置する場合の数
+
2マス目までにオオカミを配置する場合の数
.
.
.
+
Nマス目までにオオカミを配置する場合の数
となるので
dp[ N ][ 0 ]+dp[ N ][ 1 ]+...+dp[ N ][ N ]となる。
事後
なにこのDP!!!ムズイ!!!
ソースコード
class WolfInZooDivTwo { public: static const int MOD = 1000000007; // ways[i][j] = マスiまでで、最後に狼を設置したマスがjの時の // 狼の配置の仕方の数 int ways[310][310]; int count(int N, vector <string> L, vector <string> R){ // 入力 stringstream ssl(accumulate(L.begin(), L.end(), string())); vector<int> l, r; int x; while( ssl >> x ){ l.push_back( x + 1 ); } stringstream ssr(accumulate(R.begin(), R.end(), string())); while( ssr >> x ){ r.push_back( x + 1 ); } int M = l.size(); // dp初期化 memset( ways, 0, sizeof(ways) ); ways[0][0] = 1; // dp更新 for( int cell = 1; cell <= N; cell++ ){ for( int last = 0; last < cell; last++ ){ // このcellにオオカミを置く ways[cell][cell] += ways[cell-1][last]; ways[cell][cell] %= MOD; // このcellにオオカミを置かない bool ok = true; for( int k = 0; k < M; k++ ){ if( last < l[k] && r[k] <= cell ){ ok = false; break; } } if( ok ){ ways[cell][last] = ways[cell-1][last]; } } } // 集計 int res = 0; for( int last = 0; last <= N; last++ ){ res += ways[N][last]; res %= MOD; } return res; } };