ARC102-E Stop. Otherwise...
勉強になったのと,解説があまり丁寧でないのでまとめのため。
問題概要:からまでの目が出るサイコロを個振る。このとき,をみたす各について,次の問題に答えよ。
・どの異なる2つの出目の和もにならないような出目の組の場合の数はいくつか?ただし,サイコロ同士は区別しない。
解法が2つあるので,どちらも紹介する。解法2の方が簡潔である。
解法1(解説解)
を固定したときの問題を考える。を満たすのペアの個数をとする(具体的なの値はコード参照)。求める出目の総数は,個のペアについてはもしくはの片方のみの数が出現し,個のペアについてはどちらの数字も現れないような出目の総数をとすると,である。
を求めよう。戦略は以下のようになる。まず,(1)個のペアを使うと決めたときに,使用できる数の個数を求める。その次に,(2)それらの数を使った出目が何通りあるかを求める。最後に,(3)使用できる数の選び方が何通りあるか求める。これらをすべてかけ合わせた値がである。
注意する必要があるのは,が奇数と偶数のときは少しだけ事情が変わってくるということである。が偶数のとき,上のペアのうち,となるものが混入するためである。まずは,が奇数のときを考えよう。
(1) 個のペアの片方の数を必ず使うと決めたので,まず個の数が手に入る(このとき,どちらを使うかは問題にならない)。他のペアの数は使わないと決めたので,残りは,個のペアに入らない個の数たちを使う。よって,使用できる数の個数は個である。
(2) 個の数のうちから個を重複して選ぶ組合せの数なのだが,個のペアの片方の数を必ず使うと決めたので,個のうち個はもう埋まっていると考えよう。すると,残りの個を個の数で埋めてやればよい。重複組合せの記号を用いれば,個である。
(3) まず,個のペアから個のペアを求める組合せの数はである。さらに個のペアにそれぞれついて,とどちらを選ぶかが2通りあるから,が掛け算される。
以上より,が奇数のとき,は
とわかった。これをについて足し合わせれば,過不足なく数えることができる。
が偶数のときは,を使うか使わないかで別々に数えるが,別々になるのは(2)の部分のみである。
・まず,奇数のときと同様に考えるため,ペアの数はに置き換える。
・次に,(1)での使える数の個数はとしておく。というのはを差し引いたものである。((1)で求めたのは,重複を許して使うのことのできる数だったという言い方がわかりやすいだろうか。)
・(2)について,を使うとき,埋めるべき枠は個,使わないときに埋めるべき枠は個である。
・(3)はがに変わるだけである。
以上より,が偶数のときは
であり,これをについて足し合わせれば,過不足なく数えることができる。
解法2(包除原理)
包除原理がそもそもなにかということについては包除原理 - Wikipediaを参照。
解法1と同様に,を満たすのペアの個数をとし,各ペアに1からまでの番号をつけておく。集合を「出目の組み合わせのうち,番目のペアが少なくとも1つあるようなものの集合」と定義する。すると,求める組合せの総数は,集合
の要素の数である(ド・モルガンの法則を用いていることに注意)。よって,包除原理を用いての要素の個数を求め,全体の出目の組み合わせの数から引けばよい。
個のたちの共通部分の要素の大きさを求めよう。個のペアの数は使うと決めたから,個のサイコロのうち個の出目は決まっている。あとは,残りの個の枠を,個の数で埋めると考えてよい。個のたちの選び方はであるから,結局
を,の偶奇に対応して足し引きすればよい。
なんと,この解法はの偶奇に依存していない。包除原理最高である。
提出
Submission #3126896 - AtCoder Regular Contest 102
こういうのが時間内に解けるようになりたいですね。
参考
包除原理 - Wikipedia
E - Stop. Otherwise...
包除原理の解がもう少し丁寧に書いてあります。本記事と表現がちょっと違いますが、基本的な考え方は同じです。
ARC102 参加記録 - ARMERIA