AtCoder Regular Contest 067 E - Grouping
お題箱より。
解法
グループを作れる条件がなかなか扱いづらいことや制約の小ささからDPの線を考えます。
上手くDPを組むコツは「覚えておくべき情報を減らす」、逆に言うと「状態を忘れられるようにする」ことです。例えばこの問題において、「 人組を作って、 人組を作って、また 人組を作って…」という風に無秩序にグループを決めていくような考え方をすると、「これまで○人組を△つ作った」という情報を全部覚えておかなければいけません。
一方、「 のとき 人組の個数と 人組の個数には関係がない」という点に注目すると、「 人組のグループを一気に全て決めてしまう」という処理を について順番に行っていく…という考え方ができます。このとき覚えておくべき情報は「既に作られたグループで何人使ったか」だけです。それぞれの人についてグループを組める条件が違ったりはしないので、誰が使われたかの情報も必要なくて人数だけで十分です。
ということで、以下のようなDPテーブルを定義します。
: 人組のグループを全て決めてしまって、 人が使われているような場合の数
例えば として、 というのは以下のような状態を指しています。
遷移を考えましょう。 からの遷移係数は、残っている 人から 人組をいくつか組む通り数になります。 人組を 個作るとすると、 に遷移するときの係数は
という値になります。その内訳は
- : 人残っている中で使う 人を選ぶ
- : 人に対して、グループを組む 人を選ぶという処理を 回繰り返す
- :グループの区別をしないので で割る
というものです。
このとき の値と として取り得る値の最大値は反比例のようになっています。このことから調和級数の性質を用いて計算量が と評価できます。遷移のたびに を毎回計算しているとけっこう時間がかかるので注意です。