TopCoder SRM 601 Div1 Hard WinterAndShopping
問題
n個の店があって、i番目の店はfirst[i]日目に開店する。
i番目の店はred[i]個の赤い玉、green[i]個の緑の玉、blue[i]個の青い玉を持っていて、
first[i]日目から連続して、一日に一つずつを売り、全ての玉を売ったら閉店する。
同じ日に3つ以上の店が開店していることはない。
同じ日に二つの店が開店しているとき、二つの店は必ず同じ色の玉を売っている。
このとき、玉の売り方の総数をmod 10^9+7で求めよ。
制約条件
n≦50
first[i]≦500
red[i], green[i], blue[i]≦100
first[i] + red[i] + green[i] + blue[i]<500
方針
DPするだけの問題...本当に簡単だし、思いついてしかるべきなんだけど、なんか違うことをずっと考えてて浮かばなかった。酷い。
i日目に一つだけ店がオープンしているときは、赤、青の玉の個数だけを覚えていれば状態が決まる。
二つの店がオープンしているときは、先に終わるほうをA, 後に終わるほうをBとすれば、
BはAと同じ玉を売るので、Aが閉店し終えた後のBの状態は一意に決まる。
Aが閉店するまでの日数はDPしないで一気にすっとばせる。
日数のうち、赤い玉を売る日、青い玉を売る日を多項係数で求めてやるだけ。
あとは店が同時に終わる場合、同時に始まる場合などの実装を気をつけて書くだけ。
ソースコード
販売日が重なっている店を連結成分として取り出して処理している。
本当にこれで実装が簡単になったか怪しい。。。
const int mod = (int)1e9 + 7; ll C[310][310], dp[510][110][110]; ll calc(vi first, vi red, vi green, vi blue, vi end){ memset(dp, 0, sizeof(dp)); int n = first.size(); int mn = *min_element(all(first)); rep(i, n){ first[i] -= mn; end[i] -= mn; } int mx = *max_element(all(end)); dp[0][0][0] = 1; rep(i, mx){ vi v; rep(j, n) if(first[j] <= i && i < end[j]) v.pb(j); if(v.size() == 0){ rep(j, 110) rep(k, 110) (dp[i + 1][j][k] += dp[i][j][k]) %= mod; } else if(v.size() == 1){ rep(j, 110) rep(k, 110) if(dp[i][j][k]){ if(i == end[v[0]] - 1){ (dp[i + 1][0][0] += dp[i][j][k]) %= mod; continue; } if(j < red[v[0]]) (dp[i + 1][j + 1][k] += dp[i][j][k]) %= mod; if(k < green[v[0]]) (dp[i + 1][j][k + 1] += dp[i][j][k]) %= mod; if(i - first[v[0]] - j - k < blue[v[0]]) (dp[i + 1][j][k] += dp[i][j][k]) %= mod; } } else{ if(first[v[0]] > first[v[1]]) swap(v[0], v[1]); rep(j, 110) rep(k, 110) if(dp[i][j][k]){ int r = j, g = k, b = i - first[v[0]] - r - g; if(b < 0 || b > blue[v[0]]) continue; if(end[v[0]] >= end[v[1]]){ if(red[v[1]] > red[v[0]] - r) continue; if(green[v[1]] > green[v[0]] - g) continue; if(blue[v[1]] > blue[v[0]] - b) continue; int day = end[v[1]] - first[v[1]]; ll next = dp[i][j][k] * C[day][red[v[1]]] % mod * C[day - red[v[1]]][blue[v[1]]] % mod; if(end[v[0]] == end[v[1]]) (dp[end[v[0]]][0][0] += next) %= mod; else (dp[end[v[1]]][r + red[v[1]]][g + green[v[1]]] += next) %= mod; } else{ if(red[v[1]] < red[v[0]] - r) continue; if(green[v[1]] < green[v[0]] - g) continue; if(blue[v[1]] < blue[v[0]] - b) continue; int day = end[v[0]] - i; ll next = dp[i][j][k] * C[day][red[v[0]] - r] % mod * C[day - red[v[0]] + r][green[v[0]] - g] % mod; (dp[end[v[0]]][red[v[0]] - r][green[v[0]] - g] += next) %= mod; } } } } ll res = 0; rep(i, 110) rep(j, 110) res += dp[mx][i][j]; return res % mod; } class WinterAndShopping { public: int getNumber(vector <int> first, vector <int> red, vector <int> green, vector <int> blue) { rep(i, 310) rep(j, i + 1) C[i][j] = j==0||j==i ? 1 : (C[i-1][j-1] + C[i-1][j]) % mod; int n = first.size(); ll ans = 1; vi end; bool g[50][50] = {}, use[50] = {}; rep(i, n){ first[i]--; end.pb(first[i] + red[i] + green[i] + blue[i]); } rep(i, n) rep(j, n){ g[i][j] = !(first[i] >= end[j] || end[i] <= first[j]); } rep(k, n) rep(i, n) rep(j, n) g[i][j] |= g[i][k] && g[k][j]; rep(i, n) if(!use[i]){ vi f, r, gg, b, e; rep(j, n) if(g[i][j]){ f.pb(first[j]); r.pb(red[j]); gg.pb(green[j]); b.pb(blue[j]); e.pb(end[j]); use[j] = 1; } ans = ans * calc(f, r, gg, b, e) % mod; } return ans; } };