kmjp's blog

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

TopCoder SRM 681 Div1 Hard CoinFlips

SRM

これMediumでもいいんじゃ…？
https://community.topcoder.com/stat?c=problem_statement&pm=14114

問題

プレイヤーは初期状態で０ポイントである。
コインを用いたゲームでポイントを稼ぐ。

N個のコインが並んでおり、それぞれの価値はV[i]である。
以下の手順で、取り除くコインを決める。

  • 各コインを投げる。各コインは確率pで表、(1-p)で裏になる。
  • 表のコインが1個でもあれば、表のもののうち列で一番左側のものを選ぶ。なければ、列ちゅうで一番左のものを選ぶ。

両端以外のコインを取り除く時、両隣の価値の積がポイントに加算される。
その後コインを取り除き、スキマを詰める。

N回コインを取り除き、コインが無くなるとゲーム終了である。
それまでに稼ぐポイントの期待値を求めよ。

解法

初期状態でコインx,yの価値の積V[x]*V[y]がポイントに加算される確率は、元々コインx・yの間に1枚以上のコインがあり、かつコインx・yが取り除かれる前にxとyの間のコインがすべて取り除かれる確率に等しい。

メモ化再帰なりDPなりで以下の値を求めよう。
f(L,R,N) := N毎のコイン中、左からL枚目とR枚目より先に(L+1)～(R-1)枚目が先にすべて取り除かれる確率
すると解はsum(V[x]*V[y]*f(x,y,N))となる。

f(L,R,N)は以下の要領で求められる。

  • L+1=Rなら、すでに条件を満たしているのでf(L,R,N)=1
  • それ以外の場合f(L,R,N)は以下の和である。
    • (L番より左側のコインが1毎取り除かれる確率) * f(L-1,R-1,N-1)
    • (L番とR番の間のコインが1毎取り除かれる確率) * f(L,R-1,N-1)
    • (R番より右側の間のコインが1毎取り除かれる確率) * f(L,R,N-1)

全コインが裏のケースがあるので、Lが左端の場合はちょっと注意しよう。
括弧内の確率は事前に前処理をしておくとO(1)で計算できるので全体でO(N^3)で済む。
適当にメモリ確保するとMLEするので注意。

double S[305];
vector<vector<double>> memo[305];

class CoinFlips {
	public:
	double P;
	
	double pat(int L,int R,int N) {
		if(L+1==R) return 1;
		if(memo[N][L][R]>=0) return memo[N][L][R];
		double ret=0;
		
		double LP=S[L];
		double JL=(1-S[L])*P;
		double MP=(1-S[L+1])*S[R-L-1];
		double JR=(1-S[R])*P;
		double RP=(1-S[R+1])*S[N-R-1];
		double non=1-LP-JL-MP-JR-RP;
		if(L==0) JL+=non;
		else LP+=non;
		
		
		if(L) ret += LP*pat(L-1,R-1,N-1);
		ret += MP*pat(L,R-1,N-1);
		if(R<N-1) ret += RP*pat(L,R,N-1);
		
		return memo[N][L][R]=ret;
	}
	
	double getExpectation(vector <int> vals, int prob) {
		int x,y,z;
		if(prob==0 || prob==1000000000) return 0;
		P=prob/1e9;
		
		S[0]=0;
		FOR(z,303) {
			S[z+1]=S[z]+(1-S[z])*P;
			memo[z].clear();
			FOR(x,z+1) memo[z].push_back(vector<double>(z+1,-1));
		}
		
		double ret=0;
		FOR(y,vals.size()) FOR(x,y-1) ret+=pat(x,y,vals.size())*vals[x]*vals[y];
		return ret;
	}
}

まとめ

Nは200以下で良かったんじゃないかな…。