POI 11th Guesswork

問題

http://main.edu.pl/en/archive/oi/11/zga
0と1の間の小数が9個来るから、小数が来る度に、全体の何番目か推測する。全部当たる確率をできるだけ大きくする。

解法

数学(確率(と組み合わせ)、積分)+DPで解いた。より具体的には、下に書いてあるようにして解いた。
TLは 25 sec であるが、毎回計算すると流石に遅いので、前計算した。これをそのまま投げると 8 sec くらいになる。vectorを使っているが、本当はlistを使うべき。

/*
 * Guesswork
 *
 * 解法: 最適戦略を用いたときの、n=1..kのときの勝率が分かると、n=k+1のときの最適戦略と勝率を求めることができる。
 * 最終的な勝率をP(n)とする。
 * 
 * 初めは、区間(0, 1)上に、n(=9)個の数が来るとする。
 * 区間(a, b)上に数cが来たら、区間(a, c)と区間(c, b)に分け、それぞれ数がいくつ来るか予想する。
 * 区間(a, b)上にk+1個の数が来るとしていた場合は、区間(a, c)、区間(c, b)上に合計k個の数が来るとして考える。
 * 以降、一次変換をして、(a, b) -> (0, 1)として考える。(変換後のcを改めてcとする)
 * それぞれl, k-l個来て、区間(0, 1)上に来た数に関しては正しく応答できる確率はk_C_l*P(l)*P(k)*c^l*(1-c)^(k-l)となる。
 * この確率が最大になるようなlは簡単に求めることができる(cが大きくなると、そのようなlも大きくなるから、隣と比較するだけでよい)
 * 区間(0, 1)上にcが来た時の勝率が分かったから、cについて積分すると、(k+1)個の数が来る時の勝率を求められる。
 */

#include "zga.h"
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld, ld> pdd;
typedef vector<pair<pdd, int> > vecp;
#define N 9

ll C[N][N];
long double P[N+1]; // P[9]は0.0333753になる
long double sep[N+1][N+1];

vecp rg; 

ld myPow(ld a, int r){
	ld res = 1.0;
	while(r){
		if(r&1) res*=a;
		a*=a;
		r>>=1;
	}
	return res;
}

ld calc_sep(int p, int q){
	ld A = (p+1)*P[p]*P[q], B = q*P[p+1]*P[q-1]; // 式変形すると、こうなる
	return A/(A+B);
}

ld integral(int p, int q){
	ld c = sep[p+q+1][p], d = sep[p+q+1][p+1];
	ld res = 0.0;
	for(int i = 0; i <= q; i++){
		res += C[i][q-i]*(myPow(d, p+i+1)-myPow(c, p+i+1))/(p+i+1)*(1-2*(i&1)); // 展開してから、積分
	}
	return res;
}

void inicjalizuj()
{
	for(int i = 0; i < N; i++){
		C[0][i] = C[i][0] = 1;
	}
	for(int i = 1; i < N; i++){
		for(int j = 1; j < N; j++){
			C[i][j] = C[i-1][j] + C[i][j-1];
		}
	}

	P[0] = 1.0;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < i; j++){
			sep[i+1][j+1] = calc_sep(j, i-j);
		}
		sep[i+1][i+1] = 1.0;
		for(int j = 0; j <= i; j++){
			P[i+1] += C[j][i-j]*P[j]*P[i-j]*integral(j, i-j);
		}
	}
}

void nowa_rozgrywka ()
{
	rg = vecp(1, make_pair(make_pair(0, 1.0), N));
}

int kolejna_liczba (double x)
{
	int res = 1;
	for(vecp::iterator it = rg.begin(); it!=rg.end(); ++it){
		ld l = (*it).first.first, r = (*it).first.second;
		int num = (*it).second;
		if(l<=x && x<r){
			if(num==0) return 1;
			ld y = (x-l)/(r-l);
			int pos = 0;
			for(int i = 1; i <= num; i++){
				if(y<sep[num][i]){
					pos = i-1;
					break;
				}
			}
			res += pos;
			it = rg.erase(it);
			it = rg.insert(it, make_pair(make_pair(x, r), num-pos-1));
			rg.insert(it, make_pair(make_pair(l, x), pos));
			return res;
		}else{
			res += num+1;
		}
	}
	return 1;
}