この記事は Dwango Programming Contest 6th でNosubをやってしまったお詫びとして書かれたものです。このコンテストのB問題もこの記事の中で解説されます。
まず、この記事で説明する「主客転倒」とは、
得点 \(A_i\) をいくつか足した和で表される総得点 \(S_i\) が沢山あって、ありうる全ての場合について \(S_i\) を足し合わせたいときに、 \(A_i\) が何回足されるかを考えるテク
です。これだけ言われてもよくわからないと思うので、今から具体例をいくつか挙げて説明します。
まずは簡単な例から。
物理好きさんはあるゲームをした。
- \(1\) 回目では \(A_1+A_2+A_3+A_4\) 点を得た。
- \(2\) 回目では \(A_1+A_3+A_4\) 点を得た。
- \(3\) 回目では \(A_2+A_3+A_4\) 点を得た。
- \(4\) 回目では \(A_1+A_3\) 点を得た。
- \(5\) 回目では \(A_1+A_4\) 点を得た。
- \(6\) 回目では \(A_1\) 点を得た。
- \(7\) 回目では \(A_4\) 点を得た。
このゲームで物理好きさんが得た得点の総和を求めてください。
\(1 \le A_i \le 100\)
これの答えは \((A_1+A_2+A_3+A_4) + (A_1+A_3+A_4) + (A_2+A_3+A_4) ... \)
とまっすぐ数えるには少々煩わしいです。「ゲームごとの得点」を足し合わせるのではなく、「 \(A_i\) を何回足したか」を考えると楽になります。
この問題だと、 \(5 \times A_1 + 2 \times A_2 + 4 \times A_3 + 5 \times A_4\) というように、何を何回足したかという形で数えてやると楽です。
これが、「ゲームごとの得点の総和」を「\(A_i\) が足された回数」に話をすり替えた「主客転倒」です。
次も簡単な例で。
\(N\) 個の正整数 \(A_i\) があり、これを使って、以下のようなゲームを行います。
- \(N\) 回コインを投げる。
- \(i\) 回目に表が出た場合 \(A_i\) 点を得る。
- \(i\) 回目に裏が出た場合 \(0\) 点を得る。
最終的な得点は得た得点の総和です。このとき、ありえるコインの面の出かた \(2^N\) 通りについて、得られた得点の総和を足し合わせたものを \(10^9+7\) で割った余りを求めてください。
\(1 \le N \le 10^5 , 1 \le A_i \le 10^9\)
この問題で、 \(A_i\) が何回足されるかを考えます。
\(A_i\) が得点に加算されるためには、 \(i\) 回目にコインの表を出せばよく、これ以外に \(A_i\) が足されるような方法はありません。
ここで、 \(i\) 回目にコインの表が出るような場合の数は \(2^{N-1}\) 通りで、この回数だけ得点に \(A_i\) が足されます。よって、最終的な答えは \(A\) の総和の \(2^{N-1}\) 倍です。
「コインの出方」に対してそれぞれ得点を計算するのではなく、「 \(A_i\) が得点に加算される回数」を求めるに話をすりかえているので「主客転倒」です。
続いてこちら。
B - Fusing Slimes (下に示す問題文では少し言い換えています)
数直線に \(N\) 匹のスライムが左から \(1,2,...,N\) の順に並んでいて、番号 \(i\) のスライムは位置 \(x_i\) にいます。
このスライムたちに以下の操作を \(N-1\) 回行います。
- 今残っている番号 \(N\) 以外のスライムを \(1\) 匹ランダムに選ぶ。
- 選んだスライムを、今残っている中で右隣りのスライムの位置まで移動させる。
- 選ばれたスライムを消す。
ありうるすべてのスライムの選ばれ方 \((N-1)!\) 通りについて、スライムの移動距離の総和を足し合わせたものを \(10^9+7\) で割った余りを求めてください。
\(2 \le N \le 10^5 , 1 \le A_i \le 10^9\)
今度は、「主客転倒」を先に考えてみます。まず、「距離の総和」は「1回の操作の移動距離」をいくつか足し合わせたものです。「1回の操作の移動距離」は、「最初にスライム \(k\) がいる位置から、最初にスライム \(k+1\) がいる位置までの区間の長さ」をいくつか足し合わせたものです。
各区間について、それが何回答えに足されるかを考えてみましょう。「最初にスライム \(k\) がいる位置から、最初にスライム \(k+1\) がいる位置までの区間の長さ」について考えます。まず、その区間が答えに足されるためには、そもそも番号 \(k\) 以下のスライムが動かないことには話になりません。ここで、スライム \(k\) 以下にだけ注目して議論します。
- スライム \(1,2,...,k\) が \(k\) 個すべて残っている状態から \(1\) つ選ばれたとき、残っているスライムの中で一番右にあるものが選ばれたときのみ解に区間が足される。その確率は \(\frac{1}{k}\) 。
- スライム \(1,2,...,k\) が \(k - 1\) 個残っている状態から \(1\) つ選ばれたとき、残っているスライムの中で一番右にあるものが選ばれたときのみ解に区間が足される。その確率は \(\frac{1}{k - 1}\) 。
- ...
- スライム \(1,2,...,k\) が \(1\) 個残っている状態から \(1\) つ選ばれたとき、残っているスライムの中で一番右にあるものが選ばれたときのみ解に区間が足される。その確率は \(\frac{1}{1}\) 。
よって、「\(k\)番目 から \(k+1\) 番目までの区間」が足される回数の期待値は \( \frac{1}{1}\ +\ \frac{1}{2}\ +\ ...\ +\ \frac{1}{k}\) 回です。あとは対称性があるのでこれに \((N-1)!\) を掛けたものが答えです。これは逆元を使うとこのまま計算できます。
続いてこちら。
E - Change a Little Bit (下に示す問題文では少し言い換えています)
\(0\) か \(1\) からなる長さ \(N\) の文字列 \(S,T\) があります。
ありえる文字列 \(2^{2N}\) 通りについて以下で説明する「罰金」を足し合わせたものを \(10^9+7\) で割った余りを求めてください。
- \(S,T\) について、同じ位置同士で一致しない文字の数を \(c\) とする。
- \(S,T\) について、同じ位置同士で一致しない文字を \(1\) つ選んで一致させる。 \(i\) 文字目を修正するときコスト \(c \times A_i\) かかる。
- これを文字列が一致するまで繰り返す。この時必要なコストの総和の最小値が「罰金」である。
\(1 \le N \le 2 \times 10^5 , 1 \le A_i \le 10^9\)
まず、異なる文字のうち、 \(A_i\) が大きいものほどつく係数を小さくしたい(= \(i\) 文字目を修正する時点で、未修正の文字数をできるだけ減らしたい)ので後回しにするべきです。
ここで、 \(A_i\) を降順ソートしたうえで「 \(A_i\) が何回解に足されるか」を考えましょう。
まず、そもそも \(i\) 文字目が異なる必要があり、これはどの位置についても \(2^{2N-1}\) 通りです。では、 \(i\) 文字目を直すときに未修正の文字はいくつ残っているでしょうか。これは、 \(i\) 文字目を修正する時点で \(i\) 文字目より前 (すなわち、 \(A_j > A_i\) )の文字 \(j\) は最初に異なった場合残っているべきです。各文字について残っている期待値は \(\frac{1}{2}\) で、最後に \(i\) 文字目自身が残っているべきなので、係数の期待値は \(\frac{i+1}{2}\) となります。
結論、 \(A_i\) を降順ソートしたうえで \(A_i \times 2^{2N-1} \times \frac{i+1}{2}\) の総和が解となります。
最後にこちら。
この問題の「穴あき度」は、「\(S\) に含まれる白く塗られた頂点の数の期待値」、言い換えれば「ある頂点 \(i\) が \(S\) に含まれる確率の総和」です。
「ある頂点 \(i\) が \(S\) に含まれる確率」は、「 \(i\) から出る少なくとも \(2\) つの辺について、( \(i\) から見て)その先にあるノードが \(1\) つでも黒い確率」です。
この「少なくとも2つの辺に...確率」は「 \(1\ -\) (1つ以下の辺について…確率)」です。「ある辺について、その先に黒が \(1\) つでもある確率」はその先にノードが \(k\) 個ある場合 \((1-({\frac{1}{2}})^{k})\) です。これはdp[ノード \(v\) ]={ \(v\) の部分木にあるノードの数}という 木DP を使うと求められます。
<練習問題>
ネタバレ部分は反転文字で書いているので、必要があればテキストを選択して読んでください。
E - Max-Min Sums (500点問題)
「集合 \(X\) に対する \(f(X)\) の値」を [配列を昇順ソートしたうえで]「min=a , max=b となるような区間の数」に主客転倒。[同じ長さの区間は累積和でまとめて計算できる。]
Max-Min Sums [AtCoder Beginner Contest 151 E] - はまやんはまやんはまやん (上記とは別の方針での主客転倒)
<まとめ>
「和の形の数え上げ」を見たら、「主客転倒」バックで解く(「どういう「主客転倒」をすると楽に数えられそうか?」を考えて解く)とかなり楽になることが多いです。
ちなみに、この記事でやっていることは結局、「和の形のコストのまとめ方を変える」ということです。コストが積の形などで一見うまくいかなさそうな問題もうまく何らかの和の形に落とし込めばこの手法が効いたりします。(cf. C - Cookie Distribution )
さらに、これは憶測なのですが、「何かしら数えたいものをどうにかして何かしらの和の形に落とし込むとこのテクに帰着できたりする」まで全体の流れをバックで強く意識するともしかすると数え上げがもっと解けるようになるのかな…?とも思っています。これは筆者が身をもって実験していこうと思います。
では、皆さんよい「主客転倒」ライフを!
