CF Round 309 C Kyoya and Colored Balls

問題:

http://codeforces.com/contest/554/problem/C
k色ボールが全部でn個ある。
各色のボールはa[i]個ある(つまりn=Σa[i])
このボールを以下の条件を満たすように横に並べる時、その並べ方は何通りあるか。ただし同じ色のボールは区別しない。

条件: 全ての色i=1,2,...,k-1に対して、並べた色iのボールの中で一番左側にあるものをp[i]と表すと、p[i]はp[i+1]の右側にある。

入力はkと各a[i]で、制限はn<=1000, k<=1000である。

解法:

例えばk=2の場合を考えてみます。
一番左にくるのは必ず色kでなければならず、その時残りのボールの並べ方について考えてみます。
まず最初に色1のボールa[1]個を横一列に並べると、一番左に置いたもの以外の色2のボールa[2]-1個は色1のボールに割り込む形で入れていくことが可能です。
例えばa[1]=○5,a[2]=3の場合だと、まず最初に
1 1 1 1 1 2
と並べたあと残りのa[2]-1=2個のボールは
○ 1 ○ 1 ○ 1 ○ 1 ○ 1 ○ 2
この6個ある○の中のどこかに2個入れるということになります。これは重複組み合わせになっているのでconbinationを使って求めることができます。
3色以上の場合も同様で、まず最初に色1を並べる。そのあとに一番左に置いたあとに色2を並べる。その次に一番左に色3を置いたあとに置けるところに色3のボールを置いていく...というのを繰り返すことで求めることが出来ます。