diverta 2019 Programming Contest 2 E - Balanced Piles

問題はこちら

かなり論理的に考察できた気がするので解説ブログなるものを書くよ

論理的と言いつつだいぶ感覚で考えてるし僕自身よく理解していないのでわかりにくいだろうけど、解説ブログの練習くらいの気持ちで書いてるので許して

考察の流れ

DEGwerさんの数え上げpdfで解いたF - Road of the Kingになんとなく似てるなぁ

あの問題は「一見不可能そうな数え上げだけど、よく考えると持っておくべき状態はこれだけでいいのでdpで解けます」という問題だったので、今回もそれに倣って考えよう

まず「現在の最大値」は絶対に持っておかないといけない（Hが答えに関わるので）

あとは「現在の最小値の個数(=n)」も必要な気がする、これがその時とれる選択肢の個数に関わってくるので

んーでもnはだんだん減って行って、0になったら新しい値になるはずだけど、そのためには最小値より1つ大きい値の個数も持っておく必要がある？そうすると帰納的に全ての個数を持つ必要がありそう

（この辺でお絵かきをして次の2点に気がつく）

・どの数もいずれ最小値になる

・自分と同じ数が出来るのは自分が最大値Mで、最小値mがMになる時だけ

ここから、現在の最大値とその個数を持っておけば十分そうということが分かる

具体的に書くと、まず取れる選択肢は

(a)最小のやつのうち1つを最大値にする
(b)最小のやつのうち1つを最大値+kにする(1<=k<=D)

の2種類であり、dp[i][j]:最大値がjでその個数がi個とおくと漸化式は

(a):dp[i+1][j]+=dp[i][j] （最大値の値は変わらず個数が1増える） (i<Nの時のみ)
(b):dp[1][j+k]+=dp[i][j]*i! （最大値の値がj+kになり個数が1つになる）

ここで(b)にi!が付いているのは値jの個数はこれ以上増えず、やがてi個の塊として最小値になるためであり、（掛け算は可換なので）実際に最小値になるのを待たずこのタイミングで掛けてよい（はず、よくわかってない）※追記を下の方に付けた

dp[0][N]に1、残りに0を代入してこの漸化式をすればdp[H][N]が答えでありO(NH)で解ける

これをとりあえず書いて見たらサンプル2が合ったので考え方は正しいことがわかる

そのあと実際にdpを表示してみるとjの値が同じならdpの値も同じになってることに気がついて、階乗の累積和を使えばいいじゃんとなる

追記（階乗に関して）:階乗を好きなタイミングで掛けていいのは最終的に求める値が"全ての塊が最大値（H）に行った状態"、つまり全ての階乗がきちんと消費されたタイミングだから。そのため、今回dp[i][j]の値は僕が想定していた値ではなく、最終的に現在の塊が全て消えることを踏まえた値になっている。なんというか非常にラッキーな考察ミスのおかげでAC出来たんだなぁと言う感じ