AGC 025-B- RGB Coloring - 空母のブログ

AtCoder Grand Contest 025-B- RGB Coloringを解きました。

B - RGB Coloring(700点)

atcoder.jp

問題

N個のブロックを無色、赤色、青色、緑色に塗ることができる。

ブロックの色によって得点が変わる。

各ブロックは無色だと0点、赤色だとA点、青色だとB点、緑色だとA+B点でN個のブロックの得点の合計Kとなる組み合わせの数を求める。

同じブロックに複数の色は存在しない。

解き方

まず最初に、愚直に解いた場合を考えます。簡単に思いつく方法はi番目のブロックをc色で塗るという方法です。しかし、この方法だと枝刈りを考えなければ計算量は $O(4^N)$ となってしまいTLEになってしまいます。

次の方法は赤でX個、青でY個、緑でZ個塗った場合の組み合わせを考えます。計算量が $O(N^2)$ となるためこの方法もTLEになってしまいます。

そこで、緑色を赤色と青色を同時に塗ったと考えます。これによって、赤でX個、青でY個塗った場合を考えればよくなり、計算量が $O(N)$ なので間に合います。ちなみに、組み合わせの数はX,Yが整数かつ $0\leq A,B \leq N$ であるときの $comb(N,X)\times comb(N,Y)$ の総和で求まります。