SRM601D1Hard WinterAndShopping
ウーン
問題概要(原文)
$N$ 個の店がある．$i$ 番の店は $D_i$ 日目から営業を始め， 赤，緑，青色の商品がそれぞれ $R_i, G_i, B_i$ 個ある．
各店は以下の制約を満たして営業する．
- $1$ 日に $1$ 個の商品を売る．商品がなくなったら閉店する．
- 同じ日に他の店があったとき，同じ色の商品を売る
- 同じ日に営業をしている店は高々 $2$ つしかない
売られる商品の種類を表した文字列を $s$ とする． $i$ 日目に売られる商品の種類を $s_i$ は $\{ \text{'r'}, \text{'g'}, \text{'b'}, \text{'w'} \}$ のどれかである． $s$ は何通りあるか？ $\text{MOD} \; 10^9 + 7$ で求めよ． ここで， $\text{'r'},\text{'g'},\text{'b'}$ はそれぞれ，赤，緑，青色の商品が販売されることを， $\text{'w'}$ は商品が販売されない日であることを示す．
考察
$1$ 日に $0$ つの店しかやっていない場合は自明である．
$1$ 日に $1$ つの店しかやっていない場合は動的計画法を用いて，状態 $O(RG)$ ，遷移 $O(1)$ でできる(青色についての情報はなくても，経過日数と他の色の数から求められる)．
$1$ 日に $2$ つの店がやっている場合を考える．先ほどと同様の動的計画法でやろうとすると，$O(R^2 G^2)$ ぐらいかかりそうで難しい．
ここで，最大でも $2$ つの店しかやっていないことを考える．それぞれ店 $a,b$ として， $i$ 日目の時点で，商品の残っている数を $R_a,R_b,G_a,G_b,B_a,B_b$ とする． 以下の $3$ つの場合だけ考えればよい．
- 店 $a$ が店 $b$ より先に閉店する
- $R_a \leq R_b, G_a \leq G_b, B_a \leq B_b$ を満たす．
- $i + R_a + G_a + B_a$ 日目に閉店し， $R_a, G_a, B_a$ 個の種類がそれぞれ販売される
- そのような商品の売り方は $\binom{R_a + G_a + B_a}{R_a} \binom{G_a + B_a}{B_a}$ 通り
- 店 $a,b$ は同じ日に閉店する
- $R_a = R_b, G_a = G_b, B_a = B_b$ を満たす．
- $i + R_a + G_a + B_a$ 日目に閉店し， $R_a, G_a, B_a$ 個の種類がそれぞれ販売される
- そのような商品の売り方は $\binom{R_a + G_a + B_a}{R_a} \binom{G_a + B_a}{B_a}$ 通り
- 店 $b$ が店 $a$ より先に閉店する
- $R_a \geq R_b, G_a \geq G_b, B_a \geq B_b$ を満たす．
- $i + R_b + G_b + B_b$ 日目に閉店し， $R_b, G_b, B_b$ 個の種類がそれぞれ販売される
- そのような商品の売り方は $\binom{R_b + G_b + B_b}{R_b} \binom{G_b + B_b}{B_b}$ 通り
このようにしてやると， $O(R^2 G^2)$ でまとめて遷移ができるがまだ間に合わない．
ここで，店が $2$ つやっている状態にシフトした日だけこのようにしてやればよいことに気づく．そのようにすると，新しく入った店の状態は必ず $1$ 通りしかなく， $O(RG)$ で計算ができる．
さて，まとめるとこのようにすればよい．
- 店 $i$ が $D_i$ 日目に追加されるというイベントを $N$ 個用意する
- 今ただ一つ開店している店の番号を $X$ とする． $X=-1$ ならば，どの店も営業うぃていないことを表す
- 日付を $0$ から順に動かしていく
- $i$ 日目は以下の順序で処理をする
- 今見ている店が閉店したならば，$X=-1$ とする
- イベントで店の追加を処理する
- $X=-1$ ならば $X=id$ とする
- そうでないならば， $5.$ へ
- $X=-1$ ならば何もせず $i+1$ 日目の $1.$ へ
- そうでないならば $O(RG)$ で遷移を試し， $i+1$ 日目 の $1.$ へ
- $2$ つの店を上記で述べたようにまとめて処理し， 適切な日 $x$ 日目の $1.$ へ
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class WinterAndShopping
{
public int getNumber(int[] first, int[] red, int[] green, int[] blue)
{
const long MOD = (long)1e9 + 7;
var n = first.Length;
var ev = Enumerate(550, x => new List<int>());
for (int i = 0; i < n; i++)
{
first[i]--;
ev[first[i]].Add(i);
}
var dp = new long[150, 150];
dp[0, 0] = 1;
var cur = -1;
var binomial = new long[550, 550];
binomial[0, 0] = 1;
for (int i = 0; i < 520; i++)
for (int j = 0; j < 520; j++)
{
binomial[i + 1, j] += binomial[i, j];
binomial[i + 1, j + 1] += binomial[i, j];
binomial[i + 1, j] %= MOD;
binomial[i + 1, j + 1] %= MOD;
}
for (int t = 0; t < 520;)
{
if (cur != -1 && first[cur] + red[cur] + green[cur] + blue[cur] == t)
cur = -1;
if (ev[t].Count > 0)
{
foreach (var id in ev[t])
{
if (cur == -1)
{
cur = id;
var next = new long[150, 150];
next[red[id], green[id]] = dp[0, 0];
dp = next;
}
else
{
var endcur = first[cur] + red[cur] + green[cur] + blue[cur];
var endid = first[id] + red[id] + green[id] + blue[id];
if (endcur < endid)
{
var next = new long[150, 150];
for (int i = 0; i < 120; i++)
{
if (i > red[id]) continue;
for (int j = 0; j < 120; j++)
{
if (j > green[id]) continue;
var k = blue[cur];
k -= (t - first[cur]) - (red[cur] - i) - (green[cur] - j);
if (k < 0 || k > blue[id]) continue;
next[red[id] - i, green[id] - j] += ((binomial[endcur - t, i] * binomial[endcur - t - i, j]) % MOD) * dp[i, j];
next[red[id] - i, green[id] - j] %= MOD;
}
}
cur = id;
dp = next;
t = endcur;
goto NEXT;
}
else if (endcur == endid)
{
var next = new long[150, 150];
next[0, 0] = dp[red[id], green[id]] * ((binomial[endcur - t, red[id]] * binomial[endcur - t - red[id], green[id]]) % MOD);
next[0, 0] %= MOD;
dp = next;
t = endcur;
goto NEXT;
}
else
{
var next = new long[150, 150];
for (int i = 0; i < 120; i++)
{
if (i < red[id]) continue;
for (int j = 0; j < 120; j++)
{
if (j < green[id]) continue;
var k = blue[cur];
k -= (t - first[cur]) - (red[cur] - i) - (green[cur] - j);
if (k < 0 || k < blue[id]) continue;
next[i - red[id], j - green[id]] += ((binomial[endid - t, red[id]] * binomial[endid - t - red[id], green[id]]) % MOD) * dp[i, j];
next[i - red[id], j - green[id]] %= MOD;
}
}
dp = next;
t = endid;
goto NEXT;
}
}
}
}
if (cur == -1) { t++; continue; }
else
{
var next = new long[120, 120];
for (int i = 0; i < 120; i++)
for (int j = 0; j < 120; j++)
{
if (dp[i, j] == 0) continue;
var k = blue[cur];
k -= (t - first[cur]) - (red[cur] - i) - (green[cur] - j);
if (k < 0) continue;
if (i > 0) next[i - 1, j] = (next[i - 1, j] + dp[i, j]) % MOD;
if (j > 0) next[i, j - 1] = (next[i, j - 1] + dp[i, j]) % MOD;
if (k > 0) next[i, j] = (next[i, j] + dp[i, j]) % MOD;
}
dp = next;
t += 1;
}
NEXT:;
}
return (int)dp[0, 0];
}
}
コメント
- 実装がひたすら面倒なDP
- 学びはないと思う
