TopCoder SRM 471 Div2 Medium EllysPlaylists

問題概要

曲名のリストの文字列配列が与えられる。次の条件を満たすような、丁度K曲からなるプレイリストは何通り作ることができるか。
mod 1000000007で求めよ。

• プレイリストの隣り合う全ての曲について、前の曲の曲名の最後の三文字は、次の曲の曲名の最初の三文字に一致する。

1≦K≦1000,
曲名リストの要素の数は50を超えない。

解法

動的計画法による。

dp[i][j]にi回目の演奏をj曲目で行う場合の数をもっておくことで、
O(KN^2)で計算できる。

ソースコード

const int mod=1000000007;
int dp[1000][50];
bool g[50][50];

class EllysPlaylists {
	public:
	int countPlaylists(vector <string> songs, int K) 
	{
		int n=songs.size();
		rep(i,n)rep(j,n)
		{
			g[i][j]=songs[i].substr(songs[i].size()-3)==songs[j].substr(0,3);
		}
		
		rep(i,n)dp[0][i]=1;
		
		for(int i=1;i<K;i++)rep(j,n)if(dp[i-1][j])
		rep(k,n)if(g[j][k])
		{
			dp[i][k]+=dp[i-1][j];
			dp[i][k]%=mod;
		}
		
		int ans=0;
		rep(i,n)ans+=dp[K-1][i],ans%=mod;
		return ans;
	}
};

ローカルではテスト通らないので注意。（TopCoderのサーバでは一回ごとにグローバル変数が初期化されることを前提にしたコード）