TopCoder SRM 609, Division 2, Level 3 : VocaloidsAndSongs

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12989&rd=15842

問題概要

　三人の歌手がいて、S 曲からなるアルバムを作ろうとしている。全ての曲は、1 〜 3 人で歌われなければならない。更に、それぞれの歌手がアルバム中で歌う曲の総数はそれぞれ gumi, ia, mayu でなければならない。
　上記制約を満たすアルバムを作るとき、何通りの異なるアルバムを作ることができるか、MOD で求めよ。二つのアルバムが異なるとは、少なくとも一曲、異なる歌手の集合によって歌われた曲が存在することを言う。

解法

　それぞれの曲についてどの歌手の集合で歌うかを順番に決めていくとすると、状態数が になって間に合いません。ところが、確定した曲の数と各歌手が歌った回数が等しい状態は同一視することができます。従って、次のような動的計画法を考えることができます。

• dp[ i 曲確定した ][ 歌手 A が j 曲歌った ][ 歌手 B が k 曲歌った ][ 歌手 C が l 曲歌った ] := 可能なアルバムの総数

　状態遷移は、各曲についてどの歌手集合が歌うかを決めていけばよいので、j, k, l が 1 増えるかどうかを、一つも変わららない場合を除いて全通り試して遷移先の状態を計算すればよいことになります。
　計算が終わったあと、dp[ S ][ gumi ][ ia ][ mayu ] の値が問題の答えです。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

const int MOD = 1000000007;
int dp[52][52][52][51];

class VocaloidsAndSongs
{
public:
	int count( int S, int gumi, int ia, int mayu )
	{
		memset( dp, 0, sizeof( dp ) );
		dp[0][0][0][0] = 1;

		REP( i, 0, S )
		{
			REP( j, 0, gumi + 1 )
			{
				REP( k, 0, ia + 1 )
				{
					REP( l, 0, mayu + 1 )
					{
						REP( s, 1, 1 << 3 )
						{
							int &next = dp[ i + 1 ][ j + !!( s & 4 ) ][ k + !!( s & 2 ) ][ l + !!( s & 1 ) ];
							( next += dp[i][j][k][l] ) %= MOD;
						}

					}
				}
			}
		}

		return dp[S][ gumi ][ ia ][ mayu ];
	}
};