WARush

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

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について、
オオカミを配置できるかどうかを考える。

こんな場合は・・・
f:id:Ekaing:20130505113354j:plain
OK!!置いても区間内に2匹以内におさまる

こんな場合は・・・
f:id:Ekaing:20130505113445j:plain
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;
    }
};