ARMERIA

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

第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution

C - Cookie Distribution

解法

式変形と言い換え

全てのクッキーの配り方の集合を  S、答えを  A とします。答えは  (c_{1}\times\cdots\times c_{N}) の期待値に全ての配り方の通り数を掛けたものなので、 (c_{1}\times\cdots\times c_{N}) を全ての配り方について合計したもの、つまり以下のように表現できます。

 A = \displaystyle \sum_{s\in S} \left(c_{1}\times\cdots\times c_{N}\right)

実際には各  c_{i} は配り方  s に依存するので  c_{i}(s) などと書くべきですが、煩雑になるので省略しています。

期待値、および期待値とほぼ同等な数え上げ(「全ての場合について○○の値を合計したものを求めよ」タイプ)の問題で非常によく使うのが「期待値の線形性」です。確率変数の和の期待値は、それらが独立であるかどうかに関わらずそれぞれの期待値の和に分離できるので、とても強力です。

一方この問題で問われているような積の形はとても扱いにくいです。ということで、展開して和として考えましょう。

「人  i が日  d にクッキーをもらったなら  1、もらっていないなら  0」という値を  x_{id} として表記します(これも配り方  s に依存する値です)。そうすると  c_{i} = x_{i1} + \cdots + c_{iK} となります。

簡単のため  N=K=2 として、答え  A を以下のように展開してみます。

 A = \displaystyle \sum_{s\in S} \left((x_{11}+x_{12})\times(x_{21}+x_{22})\right) =  \sum_{s\in S}\left(x_{11}x_{21} + x_{11}x_{22} + x_{12}x_{21} + x_{12}x_{22}\right)

このシグマは各項ごとにばらせます。これがまさに「期待値の線形性」です。

 \displaystyle A = \sum_{s\in S}x_{11}x_{21} + \sum_{s\in S}x_{11}x_{22} + \sum_{s\in S}x_{12}x_{21} + \sum_{s\in S}x_{12}x_{22}

各項は

それぞれの人  i について「この日にクッキーをもらったかどうかに注目することにする」という日  d_{i} を選ぶ選び方

と対応しているので、それら全てについて

全ての  x_{id_{i}} 1 である、つまり全ての人  i がそれぞれ注目した日  d_{i} においてクッキーをもらっているような配り方の数

を合計したものが答えになる、と解釈することができます。図示すると以下のようなイメージです。

f:id:betrue12:20200112153100p:plain

ここまでの式変形と言い換えが第1ステップです。

DPで数える

この値をDPで求めます。先ほど見たように、答えは「それぞれの人  i が注目する日  d_{i} を選ぶ選び方」に対する「全ての人  i が日  d_{i} にクッキーをもらっている配り方の数」の合計なので、これを同時にDPで処理していかないといけません。

日を1つずつ見ていくDPを組みます。状態を以下のように定義します。

  •  1 から日  k までを見て、これらの日のクッキーの配り方が決まり、これらの日のうちのどれかを注目する日  d_{i} とするような人についてだけ  d_{i} が決まっていて、その人数が  n 人であるとする。このような状態に含まれる、「既に決まっている  n 人についての注目する日  d_{i} の選び方」と「 n 人全てがそれぞれ日  d_{i} にクッキーをもらっているようなクッキーの配り方」のペアの個数を、 dp\lbrack k \rbrack\lbrack n\rbrack とする。

ややこしいですね。例を以下のように図示します。

f:id:betrue12:20200112154840p:plain

 dp\lbrack k-1 \rbrack\lbrack n\rbrack からの遷移を考えます。 k 日目において、新しく  d_{i} = k とするような人の人数を  j とします。そうすると  dp\lbrack k-1 \rbrack\lbrack n\rbrack から  dp\lbrack k \rbrack\lbrack n+j\rbrack に遷移するときに掛かる係数は、

  • まだ  d_{i} を決めていない人  N-n 人から  j 人を選ぶ選び方  _{N-n}C_{j}
  • この  j 人にはクッキーを配ることが確定しているので、残り  a_{k}-j 枚のクッキーを渡す人を  N-j 人から選んで配る配り方  _{N-j}C_{a_{k}-j}

の積です。 j としてはこれらの2項係数が適切に定義できる、つまり  j \le \min(N-n, a_{k}) であるものだけを考えれば良いです。

これを最後まで計算すれば、 dp\lbrack K \rbrack\lbrack N\rbrack が答えになります。

まとめ

なかなか大変な問題でした。 (c_{1}\times\cdots\times c_{N}) という式をそのまま扱おうとすると、日を軸にしても人を軸にしても「それまでに○枚クッキーを配った人が△人いる」みたいな情報を分割数のようなもので細かく管理しないといけないので、今回の制約では全く間に合いません。

期待値の問題においては「数え上げの軸を変え、線形性を利用してバラし、上手く独立に計算できるようにする」というのが王道なので、 0,1 変数にバラして全部展開という多少強引な手段を使ってでも線形性を使える形に持ち込む、という考え方が重要になりました。

ACコード

Submission #9423985 - Dwango Programming Contest 6th