kmjp's blog

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

TopCoder SRM 768 : Div1 Medium PBG

本番さっくりと解けて良かったね。
https://community.topcoder.com/stat?c=problem_statement&pm=15494

問題

3種類のクマがおり、初期状態でそれぞれの数はG,P,Bである。

初期状態から、次の手順でクマを減らしていく。

  • 2体以上クマがいるとき、2体を等確率でランダムに選ぶ。
    • 選んだクマが同種なら、1/2の確率でどちらかを取り除く。
    • 選んだクマが異種なら、G,P,Bの種別の順に強いので、弱い方を取り除く。

最後に残ったクマは順位が1位となり、以降、残った時間が長い順に2位以降の順位が付く。
中央の種別のクマの順位の期待値を求めよ。

解法

N=G+P+Bとすると、普通に考えるとO(N^3)のDPは容易に思いつくが、これではTLEする。何とかO(N^2)程度にしよう。
そこで2種類のみを考える。
f(a,b) := 強い種類のクマがa体、弱い種類がb体いるとき、前者の順位の総和の期待値
これは簡単なDPでO(N^2)で求められる。

これを使い解を求めよう。
まず、前2つ(G,P)のクマをまとめて扱い、その順位の総和の期待値を求める。
次に、後ろ2つ(P,B)のクマをまとめて扱い、Gの順位の総和の期待値を求める。
前者から後者を引けばPのクマの順位の総和の期待値が求められるので、Pで割ればよい。
つまり(f(G+P,B)-f(G,P+B))/Pを答えればよい。

除算が多いため逆数を求める回数を減らす等の工夫をした方が良い。

const ll mo=1000000007;
ll memo[4040][4040];
ll rc2[6060];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class PBG {
	public:
	ll hoge(int w,int l) {
		if(w==0) return 0;
		if(memo[w][l]>=0) return memo[w][l];
		ll ret=0;
		if(l==0) {
			ret=(w+hoge(w-1,l))%mo;
		}
		else {
			if(w>=2) ret+=(w*(w-1)/2)*(w+l+hoge(w-1,l))%mo;
			if(l) ret+=(w*l+l*(l-1)/2)*hoge(w,l-1)%mo;
			ret=ret*rc2[w+l]%mo;
		}
		
		return memo[w][l]=ret;
	}
	
	int findEV(int P, int B, int G) {
		int i;
		for(i=1;i<=6000;i++) rc2[i]=modpow(i*(i-1)/2);
		MINUS(memo);
		ll GW=hoge(G,P+B);
		ll GPW=hoge(G+P,B);
		
		return (mo+GPW-GW)*modpow(P)%mo;
	}
}

まとめ

Highestにだいぶ近づけた。