SRM 258 DIV1 Hard ChutesAndLadders

問題 Editorial

問題

0〜99のマスがあるボードで複数人のプレイヤーでゲームをする。
各プレイヤーiは最初にplayers[i]のマスに居る。
各プレイヤーは各ターン、6面のサイコロを2つふり、出た目の合計だけ進む。このとき、99のマスに止まったりそこを通過した場合、そのプレイヤーの勝ちになる。
また、止まったマスがstartLadder[i]であった場合、endLadder[i]のマスにワープする。
最初にプレイヤー0のターン、そのあと順に回っていく。
各プレイヤーの勝利する確率を求めよ

• 2 <= |players| <= 4
• 0 <= |startLadder| = |endLadder| <= 20
• ¬∃i j, i ≠ j ∧ startLadder[i] = startLadder[j]
• ¬∃i j, endLadder[i] = startLadder[j]
• ¬∃i j, startLadder[i]+1 = startLadder[j] (連続した2つのマスがワープポイントであることは無い)
• 1 <= startLadder[i] <= 98
• 0 <= endLadder[i] <= 98
• 0 <= players[i] <= 98
• ¬∃i j, players[i] = startLadder[j]

解答

(各マスから * nターンで)ゴールに達する確率をDPでやる。
ここで、ある程度以上のターン数以上でゴールすることは確率が小さいので考えなくて良い。
そして、各プレイヤーに対して自分が何ターンでゴールに達するかを全探索し、それぞれに対して他の全てのプレイヤーがそのターン数未満(番号が若いなら以下)でゴールできない確率を掛け合わせる。
これには累積和を使うと良い(誤差的には、元々のDPを累積和で計算しておくほうがいいか？)
Editorialでは、「nターン以内で誰かがゴールする確率」のような感じで(n→∞)で考えていた

コメント

"rolling a `pair' typical six-sided dice"の「2つの」の部分を読み落としていて無駄に時間かかってしまった。普通に、読もう！(しかしこれは本当に注意しないと…)

コード

#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define pb(x) push_back(x)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long double ld;
int warp[100];
const int MAX = 20000;
ld dp[100][MAX+1];
ld sum[100][MAX+2];
struct ChutesAndLadders {
	ld rec(int pos, int rem_turn) {
		if(dp[pos][rem_turn] == dp[pos][rem_turn]) return dp[pos][rem_turn];
		ld r = 0.;
		if(rem_turn == 0) r = 0;
		else rer(d1, 1, 6) rer(d2, 1, 6) {
			if(pos + d1 + d2 >= 99) r += (rem_turn == 1 ? 1. : 0.) / 36.;
			else r += rec(warp[pos + d1 + d2], rem_turn - 1) / 36.;
		}
		if(r < 1e-100L) r = 0; //非正規化数対策？よくわかってないけど、多少速くなったかな？もう少し大きい値でもいい気がするけど
		return dp[pos][rem_turn] = r;
	}
	vector <double> winningChance(vector <int> startLadder, vector <int> endLadder, vector <int> players) {
		rep(i, 100) warp[i] = i;
		rep(i, startLadder.size()) warp[startLadder[i]] = warp[endLadder[i]];
		mset(dp, -1);
		rep(i, 100) {
			sum[i][0] = 0;
			rer(j, 0, MAX) sum[i][j+1] = sum[i][j] + rec(i, j);
		}
		vector<double> r;
		int n = players.size();
		rep(i, n) {
			ld p = 0;
			rer(j, 0, MAX) {
				ld q = rec(players[i], j);
				rep(k, n) if(i != k) q *= 1 - sum[players[k]][j + (k < i)];
				p += q;
			}
			r.pb((double)p);
		}
		return r;
	}
};