TopCoder SRM 817 : Div1 Hard Hagar

惜しかった…。
https://community.topcoder.com/stat?c=problem_statement&pm=17250&rd=18897

問題

整数列Aが与えられる。
これを用いて2人でゲームを行う。

まず、後手は要素のうち1つを選びブロックする。
次に、先手は要素を1つ選び、ブロックされていない要素iを選んだ場合、スコアA[i]を得る。

先手後手いずれも最適手を取るとき、先手の得るスコアの期待値は何通りか。

解法

まずA[i]=0の要素は先手は絶対に選ばないので、取り除いておく。
仮に先手がX個の要素のいずれかを狙う場合、その場合はスコアの上位X要素から選ぶことになる。わざわざそれよりスコアの低い要素を選ぶ理由はない。

以後、Xを総当たりし、スコアの期待値の最大値を考える。
複数候補があるとき、後手はスコアの大きな要素を積極的に守る。
結果的にはスコアの逆数に比例した確率で、先手はその要素をブロックされずに選択することになる。
その結果、(X-1)をスコアの逆数の総和で割った元が最大値となる。

class Hagar {
	public:
	double expectedProfit(vector <int> gold) {
		sort(ALL(gold));
		reverse(ALL(gold));
		while(gold.size()&&gold.back()==0) gold.pop_back();
		
		double ma=0;
		for(int num=1;num<=gold.size();num++) {
			double a=0;
			int i;
			FOR(i,num) a+=1.0/gold[i];
			ma=max(ma,(num-1)/a);
		}
		
		return ma;
	}
}

まとめ

二分探索案・上位X件から選ぶ案・逆数に比例する案いろいろ考えて材料は出そろってたのに、解に到達しないのは残念。