Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2012-02-09SRM531 Div1(Practice)

SRM531 Div1 300 NoRepeatPlaylist

| 02:27 | SRM531 Div1 300 NoRepeatPlaylist - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM531 Div1 300 NoRepeatPlaylist - SRM diary(Sigmar) SRM531 Div1 300 NoRepeatPlaylist - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

EasyにしてはかなりハードなDP。300だけある・・

直前のM曲は全てdistinctであることを利用すると、残り何曲演奏されていないかを記憶するDPが可能

自分は直前のM曲を除いて1回以上演奏された曲が何曲あるか記憶するというよく分からない書き方をしてしまって時間がかなりかかった。


ソースコード

const int MOD=1000000007;

class NoRepeatPlaylist {
public:
	int numPlaylists(int N, int M, int P) {
		ll res=0;
		
		ll dp[102][102];
		memset(dp, 0, sizeof(dp));
		dp[0][0]=1;
		for(int i=0; i<P; i++) {
			for(int j=0; j<=N; j++) {
				if(i<M) dp[i+1][j]=(dp[i+1][j]+(dp[i][j]*(N-i))%MOD)%MOD;
				else {
					dp[i+1][j]=(dp[i+1][j]+(dp[i][j]*j)%MOD)%MOD;
					dp[i+1][j+1]=(dp[i+1][j+1]+(dp[i][j]*(N-M-j))%MOD)%MOD;
				}
			}
		}
		res=dp[P][N-M];
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120209