kmjp's blog

競技プログラミング参加記です

TopCoder SRM 588 Div1 Easy GUMIAndSongsDiv1

SRM588に参加。
Easyは普通に解き、Mediumは1回あっさり解けたかとおもったけど方針ミスに気づき最後ぎりぎりresubmit。
…したと思ったら凡ミスでやっぱり落とした。
まぁチャレンジを1つとったおかげでレート微増・ベスト更新なので良しとするか・・・・
http://community.topcoder.com/stat?c=problem_statement&pm=12706

問題

N通りの曲があり、それぞれの長さと音の高さが与えられる。
2つの曲を連続して歌う場合、間に音の高さの差の絶対値分の時間を置かなければならない。
時間Tが与えられた場合、時間内に歌いきれる最大曲数を答えよ。

解法

歌う曲セットが決まった場合、歌う順番を音の高さ順にソートすることで、高さの差に伴う待ち時間を減らすことができる。
よって、まず曲を高さ順にソートし、DP[今まで見た曲の番号][歌った曲数]=最後の曲を歌い終わる時間という変数を使ってDPすればよい。

	int maxSongs (vector <int> duration, vector <int> tone, int T) {
		vector<pair<int,int> > V;
		int N=duration.size();
		int i;
		FOR(i,N) V.push_back(make_pair(tone[i],duration[i]));
		sort(V.begin(),V.end());
		
		int dpdp[52][52],x,y,z;
		FOR(x,52) FOR(y,52) dpdp[x][y]=1<<29;
		dpdp[0][0]=0;
		FOR(x,N) {
			dpdp[x+1][0]=0;
			dpdp[x+1][1]=min(dpdp[x+1][1],V[x].second);
			FOR(y,x) FOR(z,x+1) {
				dpdp[x+1][z+1]=min(dpdp[x+1][z+1],dpdp[y+1][z]+V[x].first-V[y].first+V[x].second);
			}
		}
		
		int ma=0;
		FOR(x,N+1) FOR(y,N+1) if(dpdp[x][y]<=T) ma=max(ma,y);
		return ma;
	}

まとめ

DP順を間違えたりして意外と手間取った。
でも普通によい問題。