Shiraz University Local Contest 2011 G, UVa-12383 : The Game

問題概要

二人用のゲームがある。1*N(<10^5)のマスがあり、初めは両端に各プレイヤーがいる。各ターン毎にプレイヤーはダイス(1~M(<10^5)の目が均等の確率で出る)を振る。プレイヤーは出たマスだけ進む。相手のいるマスに入ったら勝ちで、相手のいるマスを越えてしまったら負けになる。先手が勝つ確率を求める問題。また、出たマス丁度だけでなく1以上出たマス以下だけ動けるときは、互いに最善を尽くしたとき先手の勝率はどうなるか求める。

考えたこと

二つの問題を解かなければならないのか。
どちらもプレイヤーの間隔を状態にしてDPっぽく解くんだろう、きっと。
前者の問題について考えてみると、勝つ確率はΣ(1.0 - dp[cur-i])の計算ができれば行ける。
これは普通に組むとO(N^2)だけどBITを使えばO(N*log N)で行ける。
- 冷静に考えると累積和で足りる。
これで半分は解けた。
もう半分の方は、勝てなかったとき最も勝つ確率が低い状態を選んで移動すればいいんだからRMQを使えば行けそう。
いや、サイコロの出た目によってRMQで指定する範囲が変わるんだからBITも必要か？
冷静に式を立て直してみる。Σ(1.0 - min(dp[cur-i]))を計算しなければならない。minの範囲にjが入って…、あれこれ解けないんじゃ。O(N^3)をO(N^2)にしただけじゃ速度が足りなすぎる。
とりあえずNが小さい部分を出力させる。すると確率は単調減少になってるっぽい。
これだとminの部分がいらないからΣの部分が単なる掛け算になってO(N)に落ちる。
書く。サンプル合わない。正しい解をよく調べると単調減少になってない部分が数ヶ所見られる。
しかし殆どの部分は単調減少になっているし直前2ヶ所位覚えておいて小さい値を採用すればいいんじゃないだろうか。
これでサンプル通った。そのまま投げたら通ってしまった。

修正したコード

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_T = (int)1e5;
const double EPS = 1e-8;

int N, M;
double dp[MAX_T+1];
double accum[MAX_T+2];

void init(){
	scanf("%d%d", &N, &M);
}

double solve1(){
	dp[1] = 1.0/M;
	accum[2] = dp[1];

	for(int i=2; i<=N; i++){
		double over_prob = (i < M ? (double)(M-i)/M : 0.0);
		double win_prob = (i <= M ? 1.0/M : 0.0);
		int low = (M < i ? M : i - 1);

		double p = win_prob + 1.0/M*((double)low - (accum[i] - accum[i-low]));
		dp[i] = p;
		accum[i+1] = accum[i] + p;
	}

	return dp[N];
}

double solve2(){
	double prev = 1.0, next=1.0, prev2 = 1.0;

	for(int i=2; i<=N; i++){
		double win_prob = (i <= M ? (double)(M-i+1)/M : 0.0);
		int low = (M < i ? M : i - 1);

		next = win_prob;
		if(i == 2){
			next += (double) low / M * (1.0 - prev);
		}
		else{
			next += (double)1.0 / M * (1.0 - prev);
			next += (double)(low - 1.0) / M * (1.0 - min(prev, prev2));
		}

		prev2 = prev;
		prev = next;
	}

	return next;
}


int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
		printf("%.4f %.4f\n", solve1() + EPS, solve2() + EPS);
	}

	return 0;
}