ABC046: B - AtCoDeerくんとボール色塗り / Painting Balls with AtCoDeer

問題
考察
解法
反省
参考

問題

ABC046: B - AtCoDeerくんとボール色塗り / Painting Balls with AtCoDeer

f:id:pytwbf201830:20190104214909p:plain

考察

　まず紙に書いて実験で分かったことは下記の通り．ボールの数，色の数をそれぞれ $N$ ， $K$ とする．

ボールが $1$ 個のとき，色の数 $K$ がそのまま答えになる．
ボールが $2$ 個のとき，色の数の取り方は $_K C _{2}$ ．パターンは $1010...$ か $0101...$ の $2$ なので答えは $_K C _{2} * 2$ ．
色が $2$ 色のときは， $1010...$ か $0101...$ の $2$ 通りしかない．
ボールの大きさと色の数が等しい時， $N!$ （ $K!$ でも良い）．
ボールの大きさが色の数より小さい場合，つまり $N \leqq$ K のとき， $_K C _{N} * N!$ ．
これは，色の組み合わせを選び，それらの順列を考えることで答えが出るということ．ボールの大きさが色の数より小さくないと計算はできない．

　ここまでは考えついたが，最後にボールの大きさが色の数よりも大きいとき，つまり $N > K$ のパターンがある．この場合を考えるのは苦労した．まずは，小さい問題で考える．ボールが $4$ 個，色が $3$ 色の場合を実験してみると，

色は最低 $2$ 色で並べられる． $2$ 色をしか使わないときは，上でも述べたが $101...$ or $010...$ の $2$ パターンしかない．
上記より，使う色の数を $2$ 〜 $K$ まで好きに選べることが分かる．
つまり各色を使う時の並び方を数え上げれば良いということになる． $N = 4$ , $K = 3$ のときは， $2$ , $3$ をそれぞれ使うときに並び方何通りあるか．

　上記の考察により，この問題は $3$ 色を使って $4$ つボールの色を塗る時の並べ方の求め方が問われているんだなとなんとなく解釈できた．つまり，「 $4$ 個のボールに対して， $3$ 色を使って色が隣合わないように色を付けるパターンが何通りか？」が解ければ良い．これが分かれば $4$ ， $5$ 色，それ以上の場合の求め方も分かる．

　以上の方針で実験をしてみたのが以下の図．樹形図を用いた．これにより， $3$ 色以上を考えれば自然に $2$ 通りのときも同時に考えられ，全通りの求めた方が $K * (K - 1)^{N - 1}$ ということが分かった．実はこの式でこの問題の全てのパターンが求められる．

　考察の前半で書いた組み合わせ計算を行うと， $1000!$ などが出てきてオーバーフローが起きてしまうので注意（小さい数だとちゃんと動く）．大きな数を扱うときに階乗・組み合わせ計算を使うと大抵オーバーフローになる．あとはこれを実装してみて終わり．

f:id:pytwbf201830:20190104215003j:plain:w500:h450

　上記の考察通りに実装して提出したところ，WA と RE が出たが，オーバーフローに注意して実装したら無事 AC．

　オーバーフローに関して基本的なことが分からない方は，私の拙い記事をどうぞ．競プロを始めたばかりの方には学びがあるかもしれない．

pyteyon.hatenablog.com

解法

Official Editorial

　実装に関しては難しい点は特にない．

ABC046: B - AtCoDeerくんとボール色塗り / Painting Balls wit ...

反省

　なんとか自力 AC できた．考察に時間がかかってしまったが，最終的に決定打となったのは樹形図で，実験から導き出せたのは良かった．しかし，組み合わせ計算がオーバーフローになることを考えたり，実は最後の方で求めた式で場合分けしなくても全パターンが導けるということを思いついたりは冷静に考えれば出来たことなので悔しい．WA，RE なることは防げたであろう．

　具体的な反省点をあげるのは難しいが，考察の条件を細かく刻みすぎて問題の本質にたどり着くまで時間がかかったのは，結局力不足から来るものだろうから精進を続けるしかない．