ARC096-E「Everything on It」

Pocket

「先輩! 第2種スターリング数の勉強をしますよ!」

「え、何、どうしたの突然」

「この間のARCのE問題ですよ! あー悔しい!」

「あー、数え上げ問題だっけ。あんまり時間残ってなかったし、難しそうだったから早々に諦めちゃったよ」

「じゃあ一緒に考えましょう!」

「今日はテンション高いねー」

『Everything on It』 ラーメンを注文する問題ですね」

「どれどれ…… トッピングが N 種類あって、1杯のラーメンには、それぞれのトッピングを選んで乗せられるんだね」

「1杯のラーメンに同じトッピングを2つ以上乗せるのはダメですね」

「それで、何杯かラーメンを注文して、全トッピングを2回以上食べたいんだね」

「2回以上っていうのが厄介ですよね」

「トッピングの組み合わせが同じラーメンを重複して注文しちゃだめだから、最低でも3杯は必要か」

「”全部乗せ” と “1つだけ除外したもの” と “除外した1つ” の3種類ですね。”全部乗せ” を2杯頼むのはルール違反ですね」

「だから N ≧ 2 なんだね」

「それで、目的を達成するラーメンの組み合わせの数を計算するんですね」

「なるほど。難しそうな問題だね」

「パッと思いつくのは、”全種類2回以上食べる方法” よりも “1種類以上が1回以下しか食べられない方法” を数えるのがやりやすそうというイメージかな」

「”2回以上” だとたくさんパターンがありますけど、”1回以下” なら 0 か 1 ですもんね」

「でもそれだと “1種類以上が” というのが難しそうだね。”1種類がNG”、”2種類がNG”、…… を足していくことになるのかな」

「”NG” というのは、1回か0回しか食べられないということですね。でもその方針で考えてみたんですけど、どうもうまくいかなかったんですよね……」

「そうなんだ。じゃあどうすればいいんだろう」

「どうやら包除原理を使うみたいですよ」

「包除原理って、ベン図のあれ? 場合の数と確率でよく出てくる」

「はい! でも、競プロで包除原理を使ったことってほとんど無かったんですよね」

「僕も無いね。でも包除原理自体は分かるよ」

「集合Aの要素数を#(A)と書くとき、

#(A∪B) = #(A) + #(B) – #(A∩B)

が成り立つ、というのが基本ですね」

「3つの集合の和集合でも、

#(A∪B∪C) = #(A) + #(B) + #(C) – #(A∩B) – #(B∩C) – #(C∩A) + #(A∩B∩C)

が成り立つね」

「一般化するとこんな感じですね」

$$\#\left (\bigcup_{i=1}^nA_i \right )=\sum_{i=1}^n(-1)^{i-1}\sum_{{}_n C_i 通り}\#\left (i個選んだ積集合 \right )$$

「(-1)^(i-1)は、足すのと引くのが交互になってることを表しているんだね。最初は i=1 だから、(-1)^0 で、足すことになるんだね。Σが2個あってややこしいけど、n=3 の例で考えると、こんな感じか」

#(A∪B∪C) = {#(A) + #(B) + #(C)}{#(A∩B) + #(B∩C) + #(C∩A)} + #(A∩B∩C)

「そうですね! 最初の3つが i=1、次の3つが i=2、最後の3つが i=3 に対応しているんですね。符号も、足す・引く・足す、ですね!」

「今回の場合は、どうなるんだろう?」

「知りたい余事象は、”1種類以上のトッピングがNG” なので、”トッピング1がNG または トッピング2がNG または……” となりますよね」

「じゃあ、

“トッピング1がNG” + “トッピング2がNG” + …… – “トッピング1と2がNG” – ……

という雰囲気かな」

「そうですね! このとき、”トッピング1がNG” では、トッピング1以外がOKかNGかはどうでもいいというのがポイントですね」

「なるほど、包除原理を使うと、そう考えられるから楽なんだね」

「しかも、今回の問題では、各トッピングが対等なんですよ」

「対等? うん、確かに、トッピングごとの違いは全く無いね」

「なので、”トッピング1がNG” と “トッピング2がNG” のパターン数は同じなんですよ!」

「確かにそうだ。”1と2がNG” と “2と3がNG” も同じだね」

「なので、” i 種類がNG” として、まとめて考えられるんですよ!」

「えーっと、つまり、”とある i 種類の組み合わせがNG” のパターン数を ways(i) とすると、余事象はこうなるんだね」

$$\#(余事象)=\sum_{i=1}^N(-1)^{i-1}{}_NC_i\cdot ways(i)$$

「そうですね。N_C_i は、”とある i 種類の組み合わせ” の選び方が N_C_i 通りあることを表すんですね。トッピングについて対称性があるとも言えますね」

解説pdfにもこんな感じの式があったけど、あれは余事象使ってなかったよね?」

「いや、使ってますよ。今回の定義で、ways(0) が何を表すか、分かりますか?」

「ways(0)? うーん、”0種類がNG” で、それ以外のN種類はどうでもいいわけだから、”全種類どうでもいい” になって、実質、制限が無いのと同じ? ってことは、全事象?」

「そうです! また、N_C_0=1 ですから、ways(0) – #(余事象) が答えになるんですよ」

「そうか、だから、

$$答え=ways(0)-\sum_{i=1}^N(-1)^{i-1}{}_NC_i\cdot ways(i)$$

$$={}_NC_0\cdot ways(0)+\sum_{i=1}^N(-1)^i{}_NC_i\cdot ways(i)=\sum_{i=0}^N(-1)^i{}_NC_i\cdot ways(i)$$

になるんだね」

「そうですね。ということは、今回は N ≦ 3000 なので、ways(i) が事前計算できていれば、ここに関しては O(N) で解けますね!」

「なるほど、でも ways(i) の計算は難しそうだなあ」

「ここまでも難しかったですけど、ここからが本番ですよ!」

「ways(i) は、こんな感じだよね」

「個々のマスはトッピングを、マス内の数字は、そのトッピングを食べる回数を表しているんですね」

「うん。今は “とある i 種類の組み合わせについて、それらがNGである場合” を考えていて、選ぶ i 種類は何でも良いんだから、先頭の i 個にしても良いよね」

対称性のおかげですね! 灰色になってる部分は、ways(i) だけを考える場合は、気にしなくても大丈夫ですよね」

「そうだね。2回以上という条件を、達成していても、達成していなくても大丈夫だね」

「でも、そう単純にもいかないんですよ」

「え、どうして?」

「ここからは先頭の i 種類にのみ注目したいんですけど、灰色部分の N-i 種類が ways(i) に与える影響を考慮しないといけないんです」

「えっと、それは、N-i 種類は何でもいいんだから、2^(N-i) を掛けるとかで…… いや、そうか、何種類のラーメンを注文するかで影響が変わってくるのか!」

「そうなんですよ。たとえば、N=8, i=5 で、ラーメンを 4 杯注文した場合を考えると、

oxxox|***
xoxxx|***
xxxxo|***
xxoxx|***

のようになって、どうでもいい部分(アスタリスクの部分)の選び方が、2^(3*4)=2^((N-i)*4) 通りあるんですよ!」

「じゃあ、”ways(5) を 4 杯で達成する方法の数” には、2^((N-5)*4) を掛けないといけないけど、” 1 杯で達成する方法の数” には、2^(N-5) を掛けないといけないんだね」

「つまり、 “ways(i) を j 杯で達成する方法の数” を考えないといけないんですね。これを ways2(i, j) と書くと、ways(i) はこうなりますね」

$$ways(i)=\sum_{j=?}^{?}2^{(N-i)j}ways2(i,j)$$

「 j の値は、いくつからいくつまで考えればいいんだろう?」

「それを考えるには、ways2(i, j) についてしっかり考えないといけないですね」

「そもそも ways2(i, j) って何なんだろう?」

「 i 種類のトッピングを、j 杯のラーメンに振り分ける方法、という感じでしょうか」

「2つ以上のラーメンに振り分けちゃうと、前提に反するからダメだね。でも、どのラーメンにも振り分けられないトッピングはあっても良いんだよね?」

「ですね。”1杯以下に乗っている” というのがNGの条件なので、”0杯のラーメンに乗っている” でも大丈夫ですね」

「でもそれだと、” i 種類のトッピングが何も乗っていないラーメン” はいくらでも追加できるよね?」

「でも N 種類のトッピング全体では、同じ組み合わせのラーメンがあるとダメなルールなので、2^(N-1) 通りのラーメンを任意に追加できるという感じですね」

「うーん、ややこしいな……」

「空ラーメンは厄介なので、とりあえず、ways2(i, j) を

i 種類のトッピングを j 杯のラーメンに振り分ける方法、ただし、どこにも属さないトッピングはあっても良い。ただし、j 杯の中にトッピングが無いラーメンがあってはいけない

としましょう。こうすると、j の最大値が i (もしくは N )になります」

「最後の “トッピングが無いラーメン” というのは、先頭 i 種類のトッピングが無いってことだよね。今は考慮していない N-i 種類のトッピングだけがあっても、それはダメってことだよね」

「はい。N=8, i=5 のとき、

oxxox|oxx

は大丈夫ですが、

xxxxx|oxx

はダメです」

「つまり、言い換えると、ways2(i, j) は “区別可能な i 個のモノを空でない j 組のグループに分ける方法の数、ただし、どこにも属さないモノがあってもいい” ということだね」

「これが、第2種スターリング数に似ているらしいんですよ」

「第2種スターリング数?」

「スターリングって、階乗の近似の人?」

「スターリングの近似と同じ人っぽいですね」

「で、スターリング数って何なの?」

「ここにWikipediaの記事があります」

第2種スターリング数 (Stirling number of the second kind) は、 を下降階乗冪 の級数:

で展開したときの展開係数として定義される。

https://ja.wikipedia.org/wiki/スターリング数

「うーん、よく分からないな……」

「そこじゃなくて、その下の『組み合わせ数学における意味』の部分を見てみましょう」

第2種スターリング数 は、組合せ数学において、番号づけされた 個の要素をグループ 個に分割する組み合わせの数を与える。 分割する要素は番号付けされているので個別に区別できるが、グループは順序を特に区別しないものとする。

(中略)

要素 0, 1, 2, 3 をグループ2個に分割する組み合わせは、全部で以下の7通りがある。

https://ja.wikipedia.org/wiki/スターリング数

「なるほど、確かに似てるね」

「ways2(i, j) との違いは、どこにも属さない要素があってはいけないというところですね」

「第2種スターリング数には漸化式があるみたいだね。ということは、ways2(i, j) にも漸化式は作れるのかな」

「できそうですね。要素 i 個を j グループに分割する方法は、

① i 番目の要素が、要素数1のグループを作る

② i 番目の要素が、要素数2以上のグループに属する

③ i 番目の要素が、どのグループにも属さない

背反な3通りに分けられますよね」

「そうだね。どれも被りが無いし、たぶん漏れも無いね」

「①の場合は、i 番目の要素を抜いて考えると、i-1 個の要素が j-1 個のグループに分割されていますね」

「 i 番目を追加することで j グループになるんだね」

「②の場合は、i 番目の用をを抜いても、i-1 個の要素が j 個のグループに分割されていますね」

「 i 番目の要素は、グループ数を増やすことに貢献しないんだね」

「③の場合も同じですね。ただし、②の場合は、i-1 個の要素が振り分けられている j 個のグループのどれに i 番目の要素が入るか、によって分け方が変わりますよね」

「そうだね。でも③の場合は “どこにも属さない” の一択だから関係ないね。じゃあ、漸化式はこんな感じか」

$$ways2(i,j)=ways2(i-1,j-1)+(j+1)\cdot ways2(i-1,j)$$

「そうですね! 端の値はどうなるでしょう。ways2(0, 0), ways2(i, 0), ways(i, i) あたりが問題ですか」

「ways(0, 0) は、0種類を0グループに分割か。”グループが何もない” の 1 通りってことになるのかな?」

「そんな気がしますね。後で確認しましょう」

「 i ≠ 0 のときの ways(i, 0) は、要素 i 個を 0 グループに分割するんだけど、今回は “どこにも属さない要素があってもOK” だから、同じく “グループが何もない” の 1 通りかな」

「ways(i, i) は、全要素が単独でグループになる場合しか無いので、1通りですね。ちなみに、i < j のときは、ways(i, j) は 0 ですね。空のグループがあるといけないので」

「そうだね。これで、ways2(i, j) が、漸化式で全部計算できることになるんだね」

「 i も j も 0 から N まで考えればいいので、O(N^2) ですね。間に合います!」

「それで、空のラーメンの件はどうなったんだっけ」

「あ、そうでしたね。ways(i) を構成する選び方として、今は i 種類のトッピングが1つ以上含まれるラーメンを j 杯使う場合を考えていました。そこに、i 種類のトッピングを使わない(残りの N-i 種類のトッピングのみで構成される)ラーメンを好きなだけ追加しても問題ないんですよね」

「そうだね。それで、追加できるラーメンは 2^(N-i) 種類あるんだよね」

「はい。N-i 通りのトッピングから好きに選んだラーメンですからね」

「じゃあ、2^(N-i) 通りの中から追加するかしないかを選ぶことになって、ways(i) が 2^(2^(N-i)) 倍になるのか」

「そうですね。これが正確ですね」

$$ways(i)=2^{2^{N-i}}\sum_{j=0}^{N}2^{(N-i)j}ways2(i,j)$$

「 j の最大値は i でも大丈夫だよね」

「ですね。ways2(i, j) は j > i の範囲で 0 ですからね」

「ways2(i, j) の漸化式と、この ways(i) の式と、包除原理の式でこの問題は解けるんだね」

「はい。ただ、剰余については少し注意しないといけませんね」

「ああ、二項係数(コンビネーション)の剰余と、2^(2^(N-i)) の剰余が出てくるね」

「二項係数の剰余は、階乗の逆元で求められますね。こちらのpdfにも詳しく記載されています。n! の剰余とmod逆元を、あらかじめ計算しておけば大丈夫ですね」

$$n!\equiv (n-1)!\cdot n$$

$$(n!)^{-1}\equiv ((n-1)!)^{-1}\cdot n^{-1}$$

「なるほど、

$${}_nC_r=\frac{n!}{r!(n-r)!}\equiv n!\cdot (r!)^{-1}\cdot (n-r)!^{-1}$$

で計算できるんだね」

「2^(2^(N-i)) ですけど、これはフェルマーの小定理が使えますね」

「逆元ってこと?」

「そうじゃなくて、単純に、mod M で

$$2^{M-1}\equiv 1$$

が成立するので」

「ああ、じゃあ

$$2^{2^{N-i}}=2^{M-1}\cdot 2^{M-1}\cdot\cdots\cdot 2^{\left (2^{N-i}\%(M-1)\right )}\equiv 2^{\left (2^{N-i}\%(M-1)\right )}$$

が成立するんだね」

「さあ、コーディングしますよ!」

「ACです! やりました!」

「おおー 途中の ways2 を出力する部分も、ちゃんと正しい値を返していたね」

「いやー、疲れました。難しかったですねー」

「そうだね。ヒント無しで自力で解くのは厳しかったな」

「でも分かってしまえば解けそうな気もしてくるなー 悔しー!」

「次に包除原理の問題に当たったときは、解けるようになっておきたいね」

「AGCで包除原理来い!」

Pocket

スポンサーリンク
レクタングル大
レクタングル大

シェアする

  • このエントリーをはてなブックマークに追加

フォローする