diverta 2019 Programming Contest 2 E問題メモ
E - Balanced Piles
問題
- $N$ 個のマスがあり、はじめ、各マスに箱は1つも積まれていない
- 全てのマスに、箱がちょうど $H$ 個積み上がった状態にしたい。これを「目標の状態」とする
- 積み上げ方に以下のようなルールを設けるとき、積み上げ方は何通りあるか、$\mod{10^9+7}$ で答えよ
- ある正整数 $D$ が決められている
- 以下を、目標の状態になるまで繰り返す
- 1マスに積まれている箱の最大値を $M$ 個、最小値を $m$ 個とする
- 積まれた箱が $m$ 個であるマスをどれか1つ選ぶ
- そのマスに積まれた箱が $M$ 個以上 $M+D$ 個以下になるように1個以上箱を積む
- マスは区別するが、箱は区別しない
- $2 \le N \le 10^6$
- $1 \le D \le H \le 10^6$
解法
DPっぽい雰囲気を感じるが、状態数がとんでもないことになりそうで、実は少ない状態数で解ける問題。
問題文の通りに実装しようとすると、「何個の箱が積まれたマスが何マスあるか」、全 $O(H^N)$ の状態を持っておかねばならないように見える。 「最大値」「最小値のマス」に加え、「その最小値のマスが最小値で無くなったら次に最小値となるマス」の特定が必要だからだ。
当然、その方法では無理。
数列への転換
以下のような数列を考えると、取っかかりが見つかる。
- はじめは0が $N$ 個並ぶ
- 数列は広義単調増加
- 同じ数字は $N$ 個以下
- 隣接する数字の差は $D$ 以下
- 最後は $H$ が $N$ 個並ぶ
$N=3$ 個のマスに高さ $H=4$ 個まで、$D=2$ で箱を積むと、例えばこんな数列ができる。
0 0 0 1 3 3 4 4 4
すると、この問題において「マスに積まれた箱の個数の組合せ」の遷移は、この数列を幅 $N$ の窓で順にスライドさせた状態と一致する。
1 0 0 0 2 0 0 1 0のマスに箱を積んで1にする 3 0 1 3 0のマスに箱を積んで3にする 4 1 3 3 0のマスに箱を積んで3にする 5 3 3 4 1のマスに箱を積んで4にする 6 3 4 4 3のマスに箱を積んで4にする 7 4 4 4 3のマスに箱を積んで4にする
よって、このような数列の個数を数え上げることが、解答への一歩となる。
入れ替わりの考慮
ただしこのままだと、途中で最小値の箱が複数ある場合にどれを選んでもよいことが考慮されていない。
例えば上記では3が2つ出てくるが、数列の解釈では「3番目の操作で先に0から3にしたマスを、6番目の操作で先に3から4にする」パターンしか考えられていない。 しかし実際は、4番目の操作で後から3になったマスを、3から4にするときには先に操作してもよい。
この操作順序の入れ替わりパターンは、ある数字について同じ数字が $K$ 個あると、$K!$ 通り発生する。
0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 だと、数列としては1個でも操作パターンとしては $3! \times 3! \times 3! \times 3! = 1296$ 通り存在する。
なお、$H=4$ については次の操作が無いので、$K$ 個あっても $K!$ 倍する必要は無い。
DPの構築
これを踏まえて、DPを考える。
まず、入れ替わりを考えず、数列の個数を単純に数えるなら、以下のようになるだろう。
$DP[i]=$ 数列の右端が $i$ であるような、条件を満たす数列の個数
- $DP[0] = 1$
- $DP[i] = (DP[i-D]+DP[i-D+1]+...+DP[i-1]) \times N$
途中の数字は $D$ 個までなら飛ばしてもいいので、遷移元は $DP[i-D]～DP[i-1]$ の和となる。
これに $N$ をかけているのは、$i$ が1個、2個、…、$N$ 個並ぶパターン（全 $N$ 通り）を考慮している。
答えは、$DP[H-D]～DP[H-1]$ の和となる。 $DP[H]$ まで計算しなくていいのは、$H$ については目標の状態である $N$ 個並ぶパターンのみ数えればよいから。 （他と同様に計算すると、1個だけ並ぶパターンなどが含まれてしまう）
次に、入れ替わりを考慮して数えると、こう変化する。
- $DP[0] = N!$
- $DP[i] = (DP[i-D]+DP[i-D+1]+...+DP[i-1]) \times (1!+2!+...+N!)$
まず初期状態で、これからどの順で操作するかのパターン数が $N!$ になる。
また、先ほどの $N$ をかけていた箇所が階乗の和に変化しているが、これは $i$ が $k$ 個並ぶパターンでそれぞれ $k!$ 通りに派生するのを合計している。
階乗の和は $i$ に依らないので事前計算してしまえ、このアルゴリズムは $O(N+H)$ で動作する。
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7
fact, fact_acc = 1, 1
for i in range(2, n + 1):
fact = fact * i % MOD
fact_acc = (fact_acc + fact) % MOD
dp = [0] * h
dp[0] = base = fact
for i in range(1, h):
dp[i] = base * fact_acc % MOD
base = (base + dp[i]) % MOD
if i >= d:
base = (base - dp[i - d]) % MOD
print(base)
