SRM 222 DIV1 Hard KingOfTheCourt

問題 Editorial

問題

ゲームをする。プレイヤーがN人いて、常に一列に並んでいる。
kingと呼ばれるプレイヤーが各ターンに一人いる。
kingは次のプレイヤーとテニスの対戦をしていき、kingが勝ったなら、対戦相手は列の一番後ろに移動し、次のプレイヤーとまた対戦をする。全てのプレイヤーに一度のkingの間に勝ったならそこでゲームが終了し、kingの最終的な勝ち。
kingが負けたなら、kingのプレイヤーは列の一番に移動し、対戦相手のプレイヤーが新しいkingとなりその位置(列の一番前)に留まり、次のターンへ進む。
テニスの1回のセットで勝つ確率は、プレイヤーごとに決められた強さabilityに対し、iがjに勝つ確率は(ability[i] / (ability[i] + ability[j]))とする。
テニスの1回の対戦では、kingは1回, kingではないプレイヤーは2回 のセットの先取で勝ちが決まる。
ゲームの最初、プレイヤー0がkingである。
プレイヤー0がゲームに最終的に勝つ確率を求めよ

解答

EditorialとPractice Roomのrng_58さんの解答を参考にした。
状態として「列の順列」を持つ。このとき、列の先頭がkingで、まだ誰にも勝っていない状態を考える。
そして更新では「(i-1)回勝ってそのあと負ける」という確率を求めて足す。
あとはDPを収束するまで回すやつをやる

コメント

最初問題よくよめてなかった。しかしこれはなんとく分かりそうな気はする。

コード

#include <vector>
#include <algorithm>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
using namespace std;
typedef vector<int> vi;
struct KingOfTheCourt {
	double chancesOfWinning(vector <int> a) {
		int n = a.size();
		vi v;
		rep(i, n) v.pb(i);
		map<vi,int> permto;
		int m = 0;
		do { permto[v] = m ++; } while(next_permutation(all(v)));
		static double win[5040], prob[5040][7]; static int to[5040][7];
		sort(all(v));
		do {
			int s = permto[v];
			double p = 1;
			reu(i, 1, n) {
				vi w;
				reu(j, i, n) w.pb(v[j]);
				reu(j, 1, i) w.pb(v[j]);
				w.pb(v[0]);	//負けた後の状態だから、最後にkingが来る
				double q = a[v[0]] * 1. / (a[v[0]] + a[v[i]]);
				to[s][i] = permto[w];
				prob[s][i] = p * ((1 - q) * (1 - q));
				p *= 1 - (1 - q) * (1 - q);
			}
			if(v[0] == 0) win[s] = p;
			else win[s] = 0;
		}while(next_permutation(all(v)));
		static double dp[2][5040];
		fill(dp[1], dp[1]+m, 0.);
		rep(ii, 5000) rep(i, m) {
			dp[ii&1][i] = win[i];
			reu(j, 1, n) dp[ii&1][i] += prob[i][j] * dp[~ii&1][to[i][j]];
		}
		return dp[0][0];
	}
};