AGC002 F - F - Leftmost Ball
N色(色1～色N)のボールがそれぞれK個づつある。これらを並び替え、各色の先頭にあるボールを全て同じ色(色0)に塗る。並び方は何通りあるか？
こういう問題ではボールをノードとして捉え、ノード間の順番制約をエッジとして表現できたらトポロジカルソートの個数となる。トポロジカルソートの個数は一般に求める方法があるわけではないが、単純なグラフならdpで数える。これが基本方針。
各色だけ取り出すと「色0 色i 色i 色i...」という並びになる。その他、一番右にあるボールがすべて塗られるので、右から見ていった場合、色0のボールの数が、それまで登場した色の数よりも必ず大きくなる。なので、一旦色の順番を固定すると、結局以下のようなグラフになる。
(図はEditorialより拝借)
このトポロジカルソートとして可能な個数をカウントし、色の順番としてありうる数N!を乗じると答えになる。トポロジカルソートとして可能な個数のカウントは一般的なアルゴリズムがあるわけではないが、頑張ってdpでカウントする。O(N^2)。
