ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Regular Contest 067 E - Grouping

お題箱より。

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 に遷移するときの係数は

 \displaystyle\frac{_{n}C_{ik}(ik)!}{(i!)^{k}k!}

という値になります。その内訳は

  •  _{n}C_{ik} n 人残っている中で使う  ik 人を選ぶ
  •  \frac{(ik)!}{(i!)^{k}} ik 人に対して、グループを組む  i 人を選ぶという処理を  k 回繰り返す
  •  \frac{1}{k!}:グループの区別をしないので  k! で割る

というものです。

このとき  i の値と  k として取り得る値の最大値は反比例のようになっています。このことから調和級数の性質を用いて計算量が  O(N^{2}\log N) と評価できます。遷移のたびに  (i!)^{k} を毎回計算しているとけっこう時間がかかるので注意です。

ACコード

Submission #8719030 - AtCoder Regular Contest 067