kmjp's blog

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

Codeforces #164 Div2. E. Playlist

本番一部分最後まで詰められなくて解けなかった問題。
http://www.codeforces.com/contest/268/problem/E

問題

曲の長さと好みである確率が与えられる。
ある曲が好みの場合、それを聞いた後好みの曲のリストに加える。
曲が好みでない場合、曲を聞いた後口直しに好みの曲のリストを全部再度再生する。

このような処理を行った場合、曲順を並べ替えて総再生時間の期待値が長くなる組み合わせの再生時間を求める。

解法

曲順は後回しにして、まずは総再生時間を考える。
ある曲の再生時間がL、好みの確率がP(0<=P<=1)とする。

  • 好みでも好みでなくても1回は再生するので、総再生時間はL増える。
  • 好みの場合、好みの曲のリストの再生時間が増えるので、リスト再生時間の期待値はL*P増加。
  • 好みでない場合、総再生時間はそこまでの(リスト再生時間)*(1-P)分増える。

この性質を踏まえて、今度は曲順のソート方法を考える。
2つの曲1,2の再生時間・好みの確率をL1,L2,P1,P2とする。

先に曲1を聞く場合、総再生時間の期待値はL1+L2+L1*P1*(1-P2)。
先に曲2を聞く場合、総再生時間の期待値はL1+L2+L2*P2*(1-P1)。
よって、L1*P1*(1-P2) > L2*P2*(1-P1)なら曲1をそうでないなら曲2を先に聞く方が良い。
よってソートの比較関数で上記述語関数を用いてソートすればよい。

int N;
ll L[50001],P[50001];
vector<int> V;

bool comp(const int& a,const int& b) {
	ll as = L[a]*P[a]*(100-P[b]);
	ll bs = L[b]*P[b]*(100-P[a]);
	return as > bs;
}

void solve() {
	int f,r,i,j,k,l;
	double ss;
	int x,y;
	
	N=GETi();
	FOR(i,N) { L[i]=GETi(); P[i]=GETi(); V.push_back(i); }
	sort(V.begin(),V.end(),comp);
	
	double TT=0, S=0;
	FOR(i,N) {
		S +=L[V[i]] + TT*(100-P[V[i]])/100.0;
		TT+=L[V[i]]*P[V[i]]/100.0;
	}
	_P("%.13lf\n",S);

	return;
}

まとめ

本番は比較の述語関数が思い浮かばず回答できなかった。
でも上の様に考えると結構簡単な問題だね。