AGC025 B - RGB Coloring を形式的冪級数で解く
AGC025 B - RGB Coloring を解いた後にこの問題を Twitter で検索してみたら「形式的冪級数を使うと考察をすっ飛ばせてすごい」という声が多数ヒットしたので、 形式的冪級数を使って改めて解いてみたところ本当に「やるだけ」の問題になってびっくりしたよ~~という記事。
問題
形式的冪級数を使わない解法
(緑の点数) = (赤 + 青の点数)であることに注目すると、この問題は次のように言い換えられることが分かる:
個の無色のブロックがある。まず、 個のブロックの中からいくつか選んで赤色に塗る。その後、 個のブロックの中からいくつか選んで青色に塗る。 このとき、赤色と青色の両方の色で塗られるブロックが存在してもいい。赤色に塗られたブロックに 点、青色に塗られたブロックに 点を与えるとき (両方の色で塗られたブロックには 点が与えられることになる)、 個のブロックの合計点数が になるような色の塗り方の総数を求めなさい。
赤色に塗るブロックの個数を 、青色に塗るブロックの個数を とすると、合計点数は となる。 一方、このように色を塗る塗り方は 通りある。よって、求める答えは かつ を満たすすべての について の和を取ったものとなる。これは、 を満たす を全探索することで求められる。計算量は 。
形式的冪級数を使った解法
求める答えは を展開したときの の係数で、展開すると
となるから、 かつ を満たすすべての について の和を取ったものが答えであることが分かる。
考察要素がほとんどなくなってすごい~~