TopCoderOpen 2019 Round2B : Hard SlightlyBigger

式が立てば解くのは簡単だが、そこまでの考察が難しい。
https://community.topcoder.com/stat?c=problem_statement&pm=15527

問題

2人で互いに任意の正整数を選ぶゲームを行う。
その結果に応じて、以下のように得点が入る。

• 選んだ値が同じなら引き分けで双方得点なし。
• 数に差があった場合、
  • 差がD以下の場合、大きい方の値を答えた方N点を相手からもらう
  • 差がDより大きい場合、小さい方の値を答えた方F点を相手からもらう
  • なお、FはN以上である

互いに最適手を打つ場合、正整数Qが最適手である確率はいくつか。

解法

下記Codeforcesのコメントを参考に解いた。
TCO19 Round 2B - Codeforces

f(n) := nと答えるのが最適である確率
とする。
いくつか考察にステップがいる。

• 互いに最適手を取るので、
  • 互いにある手を出すのが最適な確率は同じ。
  • 互いに得点の期待値は釣り合う状態、すなわち0になる。
• F≧Nなので、大きすぎる値はデメリットが大きい。むしろ小さい値が好ましいので、f(1)＞0となる。
  • f(1)＞0ということは、相手がそれを読んでD+1程度までの値を出してくる可能性があるので、自分は高々(2D+1)までしか選択肢はない。仮に相手がD+1より大きな値を出す場合、それを上回る値を狙うよりは、1を出した方が良いためである。

よって、以下の式を立てる。

• f(1)～f(2D+1)の和は1
• 自分が1～(2D+1)まで出したときの得点の期待値はそれぞれ0

変数が2D+1個で、式が2D+2個なのでf(1)～f(2D+1)が求まる。

// M*r+v=0となるr
// 返り値はrank
const int MAT=301;
double ma[MAT][MAT],V[MAT],R[MAT];
int Gauss(int n,double mat_[MAT][MAT],double v_[MAT],double r[MAT]) {
	int i,j,k;
	double mat[MAT][MAT],v[MAT];
	memmove(mat,mat_,sizeof(mat));
	memmove(v,v_,sizeof(v));
	
	FOR(i,n) {
		if(mat[i][i]==0) {
			for(j=i+1;j<n;j++) if(mat[j][i]) break;
			if(j>=n) return i;
			FOR(k,n) swap(mat[i][k],mat[j][k]);
			swap(v[i],v[j]);
		}
		v[i]/=mat[i][i];
		for(k=n-1;k>=i;k--) mat[i][k]/=mat[i][i];
		for(j=i+1;j<n;j++) {
			v[j]-=v[i]*mat[j][i];
			for(k=n-1;k>=i;k--) mat[j][k]-=mat[i][k]*mat[j][i];
		}
	}
	
	for(i=n-1;i>=0;i--) {
		for(j=n-1;j>i;j--) v[i]-=mat[i][j]*v[j],mat[i][j]=0;
		r[i]=v[i];
	}
	return n;
}


class SlightlyBigger {
	public:
	double getProbability(int D, int N, int F, int Q) {
		if(Q>2*D+1) return 0;
		
		ZERO(ma);
		ZERO(V);
		int x,y,i;
		for(x=1;x<=2*D+1;x++) {
			ma[0][x-1]=1;
			for(y=1;y<=2*D+1;y++) {
				if(y>x+D) ma[x][y-1]=F;
				else if(y>x) ma[x][y-1]=-N;
				else if(y<x-D) ma[x][y-1]=-F;
				else if(y<x) ma[x][y-1]=N;
			}
		}
		V[0]=1;
		Gauss(2*D+1,ma,V,R);
		
		
		return R[Q-1];
		
	}
}

まとめ

シンプルな問題設定だけど、よくこういうの思いつくなぁ。