WARush

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

SRM659 Div1 Medium "CampLunch"

考えたこと

結論から言うと、1 * 2のタイルをN * Mに敷き詰める時のパターン数え上げと同じ考えのbitDPでいけちゃう。毎日人の配置が変わっているためbitDPが適用できないと思いきや、そうでもなかった。

下の図にbitDPの途中結果を描いた。
f:id:Ekaing:20150522005658j:plain

赤くなっているday1 Aが着目しているマスである。
赤の部分・・・当日のAがパターンを選べない可能性があるため(前日のAがパターン2、もしくは当日のBがパターン1)、当日のAの情報は必要。
青の部分・・・当日のAがパターン1を使えるかどうかを判断するため、隣人である当日のCの情報も持っておきたい。
黄の部分・・・翌日のB, Dはパターンを選べなくなっている可能性があるため(当日のB, Dがパターン2)、翌日のB, Dの情報も後々のために必要。
後はいらん。

人の配置が変わることで、これらの情報が不足したり競合することはない。やったぜ。


ソースコード

// dp[flag][bit]
// flag...0 | 1 参照元と更新先を表してるだけ
// bit ...0 | 1 パターンが選べない(食事済み)なら1
long long dp[2][1 << 16];
const long long MOD = 1000000007;

class CampLunch {
public:

    int count(int N, int M, vector <string> a) {

        // DP初期化
        for (int bit = 0; bit < 1 << M; bit++) {
            dp[0][bit] = dp[1][bit] = 0;
        }
        dp[cur][0] = 1;

        // DP更新
        int cur = 0;
        int next = 1;
        for (int day = 0; day < N; day++) { 
            for (int mi = 0; mi < M; mi++) {
                int me = a[day][mi] - 'A'; // 着目している人
                int nei = -1;              // 着目している人の隣の人
                if (mi + 1 != M) {
                    nei = a[day][mi + 1] - 'A';
                }

                for (int bit = 0; bit < 1 << M; bit++) {
                    if ((bit & (1 << me)) == 0) {
                        // 着目している人(赤)がパターン選べる
                        if (nei != -1 && (bit & (1 << nei)) == 0) {
                            // 隣の人(黄)がパターン選べる
                            // パターン1
                            add(dp[next][bit | (1 << nei)], dp[cur][bit]);
                        }
                        
                        // パターン2
                        add(dp[next][bit | (1 << me)], dp[cur][bit]);

                        // パターン3
                        add(dp[next][bit], dp[cur][bit]);
                    }
                    else {
                        // 着目している人(赤)がパターン選べない
                        // 次の日はパターン選べるようになる
                        add(dp[next][bit - (1 << me)], dp[cur][bit]);
                    }
                }

                // メモリ交換
                cur = 1 - cur;
                next = 1 - next;
                for (int bit = 0; bit < 1 << M; bit++) {
                    dp[next][bit] = 0;
                }
            }
            
        }

        // N日目は食事しちゃダメだからbitは0
        return (int)dp[cur][0];

    }

    void add(long long &tar, long long add) {
        tar += add;
        if (tar >= MOD) tar -= MOD;
    }
};