https://beta.atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_f
解法
https://beta.atcoder.jp/contests/maximum-cup-2018/submissions/2313017
動的計画法で解く。
唐突な感じがするが、以下のことからdpを導く。
- mod10^9+7
- Kがとても小さいので(2^5)^3がイケる
「dp[i][wmsk][ymsk][tmsk] := i日目まで決定していて和食の過去K日間の献立に和食が含まれるマスクwmsk, 洋食が含まれるマスクymsk, 中華が含まれるマスクtmskである組み合わせ数」
あとは、全てのメニューを選択した場合の遷移を書いて答え。
遷移を全てミス無く列挙することと、マスク管理が少し大変である。
マスクは下に1ビット動かし、場合によっては最上位ビットを立てることで日付の変更と選択を行うと良い。
int N, K, L; mint dp[404][1<<5][1<<5][1<<5]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K >> L; dp[0][0][0][0] = 1; int ad = 1 << (K - 1); rep(i, 0, N) rep(wmsk, 0, 1 << K) rep(ymsk, 0, 1 << K) rep(tmsk, 0, 1 << K) { int wmsk2 = (wmsk >> 1) + ad; int ymsk2 = (ymsk >> 1) + ad; int tmsk2 = (tmsk >> 1) + ad; // 和食 if (__builtin_popcount(wmsk2) <= L) dp[i + 1][wmsk2][ymsk>>1][tmsk>>1] += dp[i][wmsk][ymsk][tmsk]; // 洋食 if (__builtin_popcount(ymsk2) <= L) dp[i + 1][wmsk >> 1][ymsk2][tmsk >> 1] += dp[i][wmsk][ymsk][tmsk]; // 中華 if (__builtin_popcount(tmsk2) <= L) dp[i + 1][wmsk >> 1][ymsk >> 1][tmsk2] += dp[i][wmsk][ymsk][tmsk]; // 和食洋食 if (__builtin_popcount(wmsk2) <= L and __builtin_popcount(ymsk2) <= L) dp[i + 1][wmsk2][ymsk2][tmsk >> 1] += dp[i][wmsk][ymsk][tmsk]; // 和食中華 if (__builtin_popcount(wmsk2) <= L and __builtin_popcount(tmsk2) <= L) dp[i + 1][wmsk2][ymsk >> 1][tmsk2] += dp[i][wmsk][ymsk][tmsk]; // 洋食中華 if (__builtin_popcount(ymsk2) <= L and __builtin_popcount(tmsk2) <= L) dp[i + 1][wmsk >> 1][ymsk2][tmsk2] += dp[i][wmsk][ymsk][tmsk]; // 和食洋食中華 if (__builtin_popcount(wmsk2) <= L and __builtin_popcount(ymsk2) <= L and __builtin_popcount(tmsk2) <= L) dp[i + 1][wmsk2][ymsk2][tmsk2] += dp[i][wmsk][ymsk][tmsk]; } mint ans = 0; rep(wmsk, 0, 1 << K) rep(ymsk, 0, 1 << K) rep(tmsk, 0, 1 << K) ans += dp[N][wmsk][ymsk][tmsk]; cout << ans << endl; }
