SRM578 Div2 Hard "WolfInZooDivTwo"

問題

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

訳

パステル君は一人でまっすぐな道を歩いていた。
彼は警戒している。
なぜならこの道にはオオカミがいることを耳にしていたからだ。

道はN個のマスで構成されている。
そのマスは順番に番号が0～N-1と振られている。
それぞれのマスには、オオカミが高々１匹徘徊している。

あなたはオオカミの位置にに関する情報をM個持っている。
その情報は、この区間に少なくとも１匹のオオカミが
徘徊しているというものである。
より正確には、あなたはleftとrightという２つの整数のリストを持っている。
その意味は、left[i]～right[i] ( 0 <= i <= M-1 )の範囲のマスには、
少なくとも１匹のオオカミがいる、というものである。

あなたは２つの文字列のリスト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マスにオオカミを配置しない時

与えられた区間には、１匹以上配置しなければならないという制約があるので、
考えているcell, lastでcellマスに配置しなくて大丈夫なのかをまず判定する。

この場合は・・・

区間内に既にオオカミがいるんだから当然ＯＫ！！

この場合は・・・

ＯＫ！！だって次以降のマスに配置すればいいも～ん

この場合は・・・

ＮＧ・・・区間内に１匹は配置しなきゃね

この場合は・・・

これまたＮＧ・・・そのcellには必ず配置しなきゃダメだね

という訳で、last < left[i] かつ right[i] <= cellな区間が存在した場合、
ＮＧとなる。

ＯＫなcell, lastでは
dp[ cell ][ last ] = dp[ cell-1 ][ last ]となり、
ＮＧなcell, lastでは
dp[ cell ][ last ] = 0となる。

結果

全くオオカミを配置しない場合の数
+
１マス目までにオオカミを配置する場合の数
+
２マス目までにオオカミを配置する場合の数
.
.
.
+
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;
    }
};