問題

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_f

考え方

操作の結果の文字列を考えていく。ある文字列が構成されていると仮定したときに次の文字を置くことができる場合は、赤/青のボールごとに考えればシンプルに求めることができる。

DPを考えよう。合計で赤い R のボールが $R$ 個、青い B のボールが $B$ 個あるとする。

$dp[r][b] :=$ 結果の文字列で R を $r$ 個、 B を $b$ 個使うときの場合の数

と定義しよう。このとき次の文字列になりうることができる場合を考えよう。赤いボールの場合について考える。 $r+b$ 個の文字列が構成されていて、次の文字列になりうるのは、 $r+1$ 番目の赤いボールを $r+b$ 番以内のすぬけ君が持っている場合である。青いボールの場合も同様に考えることができる。