CSAcademy Round #28 : E. Metal Examination

こちらも手こずった。
https://csacademy.com/contest/round-28/task/metal-examination/

問題

Gグラムの金属がある。
これは均一な確率でN種類の金属のいずれである。

各金属iに対し、グラムあたりの価格P[i]と検査にかかる量C[i]が与えられる。

金属を任意の順で検査することを考える。
ある金属であるかどうかを判断する際、C[i]の量がかかり、検査に用いた分は変質するため手持ちの金属から減らされる。
検査後、もし手持ちの金属が検査対象の金属である場合、残った金属の量×グラム当たり価格の金額を得られる。

最適な順で検査を行う場合、得られる金額の期待値を求めよ。

解法

順番を求める問題なので、定番テクとして２種類の金属でどちらを先に検査した方が得か考えよう。
手持ちの金属がa,bのいずれかである場合、a→bとb→aそれぞれの順で得られる金額を考える。

• 最初に(a,b)の順で検査した場合、
• 最初に(b,a)の順で検査した場合、

両者の差を取ると、ならaを先に検査した方が良いとわかる。
よって以下、P,Cは上記判定条件をもとに順に並べたとする。

さて、サンプルを見るとわかるが、この問題はもうひとひねりする必要がある。
金属はN種類のいずれかであることがわかっているので、(N-1)回検査して当たらなければ、最後検査することなく残り1個であるとわかる。
ではどれを検査しないで済むか。

いっそ検査しないものを総当たりし、期待値がどうなるか考えよう。
まずは全部上記の順で検査した場合の期待値Eを求めておく。
仮にx番を検査しないことにした場合、x番以降の金属を検査するときの残量がC[x]増加する。
一方、x番があたりの場合、x番を除き全部の検査が終わったあとの残量分しか金属が残らない。
よってだけ増減する。

ll N,G;
pair<ll,ll> A[101010];
ll L[101010];
ll S[101010];

bool hoge(pair<ll,ll>& a,pair<ll,ll>& b) {
	return a.second*b.first < b.second*a.first;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>G;
	FOR(i,N) cin>>A[i].first>>A[i].second;
	sort(A,A+N,hoge);
	for(i=N-1;i>=0;i--) S[i]=S[i+1]+A[i].first;
	
	ll tot=0;
	FOR(i,N) {
		G-=A[i].second;
		L[i]=G;
		tot += L[i]*A[i].first;
	}
	ll ma=tot;
	FOR(i,N) {
		ma=max(ma,tot+S[i+1]*A[i].second-L[i]*A[i].first+(L[N-1]+A[i].second)*A[i].first);
	}
	
	ll g=__gcd(ma,N);
	cout<<ma/g<<" "<<N/g<<endl;
	
}

まとめ

検査しない金属の処理でてこずった。