SRM659 Div1 Medium "CampLunch"
考えたこと
結論から言うと、1 * 2のタイルをN * Mに敷き詰める時のパターン数え上げと同じ考えのbitDPでいけちゃう。毎日人の配置が変わっているためbitDPが適用できないと思いきや、そうでもなかった。
下の図にbitDPの途中結果を描いた。
赤くなっている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; } };