AtCoder Beginner Contest 132 D問題
初めてＤ問題を解けたのでメモ。
解法
赤のボールをすべて並べる。
🔴🔴
青のボールをおけるのは下図の''○"の箇所。
○🔴○🔴○
青のボールをi回で取る場合、青のボールはi個に分けられている。
3つ青のボールをi回で回収するため、ボールをi個グループに分けたい場合、3-1個ある"/"のうち、i-1個選択した場合の組分けを考えれば良い。
🔵/🔵/🔵
2つのグループに分けたい場合は、1つの"/"を選択すれば良いので、
🔵/🔵🔵 または 🔵🔵/🔵
の2通りとなる。
作成したi個のグループと等しい数だけ"○"を選択し、そこに青のボール入れた時の組み合わせを考えれば良い。
これは、赤のボールの数と"○"の数の合計からi個の"○"を選択する組み合わせ数と、青のボールの数と"/"の数の合計からi-1個の"/"を選択する組み合わせの積になる。
注意として、青のボールが赤のボールより多いときがある。
その場合、"○"の数よりも青のボールのグループ数の方が多くなる組み合わせを出力することになるが、その組み合わせは0通りとなる。
