SRM 222 DIV1 Hard KingOfTheCourt
問題
ゲームをする。プレイヤーが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]; } };