WARush

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

SRM576 Div1 Medium "TheExperiment"

問題

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

スポンジがどれほど水分を含むことになるのかという実験を行っている。
この実験が行われている部屋は側面が密閉されているため、2次元として考える事が出来る。

この部屋は幅がNセンチメートルあり、
天井にN個のドロップカウンター(雫を垂らす機械)が設置されている。
ドロップカウンター No.0 は部屋の左端から0.5センチの所に設置されており、
それから右側に1センチ間隔で No.N-1までのドロップカウンターが設置されている。
各ドロップカウンターの1分間に雫を垂らす回数が分かっている。

この部屋にはM個のスポンジがある。
全てのスポンジは長さがちょうどLセンチであり、厚さは無視できる程薄くなっている。
スポンジは水平に、スポンジ全体が部屋の中に入っていて、
部屋の左の壁からの距離は整数でなくてはならない。
言い換えれば、スポンジの左端の位置は0~N-Lの整数である。
それぞれのスポンジはその場所に落ちてきた雫を完全に吸収する。
例えば、この図では、それぞれのスポンジは
上から下に向かって、12, 5, 3の雫を1分間で吸収する。

この実験では、各スポンジが1分間で吸収する雫の数が、
AからBの間でなくてはならない。
スポンジの置き方が何通りあるのかを知りたい。
2つのスポンジの設置の仕方P, Qが同じであるとは、
Pの各スポンジをS1,Qの各スポンジをS2とした時に、
各S1とS2の雫を受けるドロップカウンターのセットが、
全く同じである場合のみである。

ドロップカウンターの情報、M,L,A,Bが与えられるので、
スポンジの設置の仕方が何通りあるかを返せ。

制約

1 <= N <= 300
1 <= M <= 300
1 <= L <= N
1 <= A <= 2700
A <= B <= 2700


考えた事

スポンジを上から下に設置していく、と考えると難しいので、
スポンジを1~Lまでに切って横一列に設置していくことにする。

こうすれば、左端からスポンジを埋めていくことができ、
DPが使えるようになる。

置き方のよい例ダメな例

f:id:Ekaing:20130413033736j:plain
スポンジの受ける雫の量をAからBの間にすることと、
長さが不完全なスポンジは、
長さLの完全なスポンジにくっついてなければならない。
完全なスポンジにくっついている不完全なスポンジにくっついていてもよい
(あぁ説明が下手・・・)

不完全なスポンジ

今考えているインデックスの前に、不完全なスポンジが来ていたとする。
f:id:Ekaing:20130413034503j:plain
上の図だとインデックス2をどうしようかな~と考えている。

①不完全なスポンジを続けておく場合
インデックス4さん、不完全なスポンジ来てますよ~と更新する。
②完全なスポンジを続けておく場合
インデックス3さん、完全なスポンジが来てますよ~と更新する。
③スポンジを置かない
そのような置き方はできないので何もしない。

完全なスポンジ

今度は今考えているインデックスの前に、完全なスポンジが来ていたとする。
f:id:Ekaing:20130413034850j:plain
上の図だとインデックス3をどうしようかな~と考えている。

①不完全なスポンジを続けておく場合
不完全なスポンジでも既に完全なスポンジがくっついているので、
インデックス5さん、完全なスポンジ来てますよ~と更新する。
②完全なスポンジを続けておく場合
インデックス6さん、完全なスポンジが来てますよ~と更新する。
③スポンジを置かない
インデックス4さん、くっついてないけど完全なスポンジが来てたよ~
と更新する。

この考え方は

自分でもなんで正しいのか分かってないです。
ヒント程度に見てもらえればと思います。



ソースコード

const int MOD = 1000000009;

int a[310];
bool can[310][310];
int dp[310][310][3]; 

class TheExperiment {

public:

    void add( int& a, int& b ){
        a = (a + b) % MOD;
    }

    int countPlacements(vector <string> intensity, int M, int L, int A, int B){
        // 配列にする
        int n = 0;
        for( int i = 0; i < intensity.size(); i++ ){
            for( int j = 0; j < intensity[i].length(); j++ ){
                a[n++] = intensity[i][j] - '0';
            }
        }

        // canを初期化
        // can[i][len] - index iに長さlenのスポンジを置けるか?
        memset( can, false, sizeof(can) );
        for( int len = 1; len <= L; len++ ){
            for( int i = 0; i <= n - len; i++ ){
                int t = 0;
                for( int j = 0; j < len; j++ ){
                    t += a[i+j];
                }
                can[i][len] = (A <= t && t <= B);
            }
        }

        // dpを初期化
        // dp[i][j][k] index iまでに j個スポンジを置いて、
    // k=0 ... 不完全なスポンジが来てる 
        // k=1 ... 完全なスポンジが来てたけどくっついてない
        // k=2 ... 完全なスポンジが来て、しかもくっついている
        // というスポンジの置き方の数
        memset( dp, 0, sizeof(dp) );
        for( int i = 0; i < n; i++ ) dp[i][0][0] = 1;

        // dpを更新
        for( int i = 0; i < n; i++ ){
            for( int j = 0; j < M; j++ ){
                // 0
                for( int len = 1; len <= L; len++ ){
                    if( can[i][len] ) 
                        add( dp[i+len][j+1][len==L?2:0], dp[i][j][0] );
                }

                // 1
                for( int len = 1; len <= L; len++ ){
                    if( can[i][len] ) 
                        add( dp[i+len][j+1][len==L?2:0], dp[i][j][1] );
                }
                add( dp[i+1][j][1], dp[i][j][1] ); // 置かない場合

                // 2
                for( int len = 1; len <= L; len++ ){
                    if( can[i][len] ) 
                        add( dp[i+len][j+1][2], dp[i][j][2] );
                }
                add( dp[i+1][j][1], dp[i][j][2] ); // 置かない場合
            }
        }

        int res = 0;
        for( int i = 0; i <= n; i++ ){
            add( res, dp[i][M][1] );
            add( res, dp[i][M][2] );
        }

        return res;
    }
};