AtCoder Regular Contest 067 E - Grouping

お題箱より。

解法

グループを作れる条件がなかなか扱いづらいことや制約の小ささからDPの線を考えます。

上手くDPを組むコツは「覚えておくべき情報を減らす」、逆に言うと「状態を忘れられるようにする」ことです。例えばこの問題において、「 $x$ 人組を作って、 $y$ 人組を作って、また $x$ 人組を作って…」という風に無秩序にグループを決めていくような考え方をすると、「これまで○人組を△つ作った」という情報を全部覚えておかなければいけません。

一方、「 $x \ne y$ のとき $x$ 人組の個数と $y$ 人組の個数には関係がない」という点に注目すると、「 $x$ 人組のグループを一気に全て決めてしまう」という処理を $x = A, A+1, ..., B$ について順番に行っていく…という考え方ができます。このとき覚えておくべき情報は「既に作られたグループで何人使ったか」だけです。それぞれの人についてグループを組める条件が違ったりはしないので、誰が使われたかの情報も必要なくて人数だけで十分です。

ということで、以下のようなDPテーブルを定義します。

$dp\lbrack i \rbrack\lbrack j \rbrack$ ： $A, A+1, ..., i$ 人組のグループを全て決めてしまって、 $j$ 人が使われているような場合の数

例えば $A = 2, B = 5, N = 15$ として、 $dp\lbrack 3 \rbrack\lbrack 7 \rbrack$ というのは以下のような状態を指しています。

f:id:betrue12:20191201142550p:plain

遷移を考えましょう。 $dp\lbrack i-1 \rbrack\lbrack N-n \rbrack$ からの遷移係数は、残っている $n$ 人から $i$ 人組をいくつか組む通り数になります。 $i$ 人組を $k$ 個作るとすると、 $dp\lbrack i \rbrack\lbrack N-n+ik \rbrack$ に遷移するときの係数は