dwangoプログラミングコンテスト予選 : C - ゲーマーじゃんけん

実際これ勝者決めに使ってるのかな。
http://dwango2015-prelims.contest.atcoder.jp/tasks/dwango2015_prelims_3

問題

以下の変則じゃんけんをゲーマーじゃんけんと呼ぶ。
皆がグーチョキパーを出すのは通常のじゃんけんと同じだが、勝者の判定方法が以下の通りである。

• 皆同じ手ならあいこ
• そうでなければ、出た数が最小の手を探す。
  • 最小の手が１種類なら、その手を出した人が勝利
  • 最小の手が２種類なら、その２種類のうち通常のじゃんけんで強い方の手を出した人が勝利
  • 最小の手が３種類なら、あいこ

N人でゲーマーじゃんけんを行い、勝ち抜き戦を行う。
最後１人の勝者が決まるまでのじゃんけん回数の期待値を求めよ。

解法

人数xに対しメモ化再帰する。
グーチョキパーの人数を総当たりし、上記勝利条件に基づき状態遷移させていけば良い。

当然グーチョキパーの総当たりを3^nかけると時間が間に合わないので、グーa人、チョキb人、パー(n-a-b)人となる組み合わせは通りあることを用いると、総当たりはO(n^2)で済む。

int N;
double memo[101];
static const int N_=1020;
static double C_[N_][N_];

double dodo(int n) {
	
	if(n==1) return 0;
	double& ret=memo[n];
	if(ret>=0) return ret;
	int i,x,y;
	double tot=0,cnt=0,ng=0;
	
	for(x=0;x<=n-1;x++) for(y=0;x+y<=n-1;y++) {
		double np=C_[n-1][x]*C_[n-1-x][y];
		int V[3]={x+1,y,n-1-x-y};
		
		sort(V,V+3);
		if(V[1]==0 || V[2]==V[0]) ng+=np;
		else {
			cnt+=np;
			tot+=np*dodo(V[0]?V[0]:V[1]);
		}
	}
	
	return ret = (cnt+ng+tot)/cnt;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,N_) C_[i][0]=C_[i][i]=1;
	for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j]);
	
	cin>>N;
	FOR(i,N+1) memo[i]=-1;
	_P("%.12lf\n",dodo(N));
	
}

まとめ

ここまではすんなり。