SRM 248 DIV1 Hard ClockManagement

問題 Editorial

問題

略

解答

(ターン * 残り時間 * スコア)でゲームDPするだけ

コード

#include <vector>
#include <cstring>
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi;  
double dp[2][333][333];
struct ClockManagement {
	vi p[2], b[2]; int s[2]; int n;
	double rec(bool turn, int t, int score) {
		if(dp[turn][t][155 + score] == dp[turn][t][155 + score]) return dp[turn][t][155 + score];
		double r = -100;
		if(t == 0) {
			r = (score * 2 + s[0] > s[1]) ^ turn;
		} else {
			rer(i, 2, min(t, 2+n-1)) {
				r = max(r,
					(p[turn][i-2] / 100.) * (1 - rec(!turn, t - i, score + (!turn ? 1 : -1))) +
					(1 - p[turn][i-2] / 100.) * (b[turn][i-2] / 100.) * rec(turn, t - i, score) +
					(1 - p[turn][i-2] / 100.) * (1 - b[turn][i-2] / 100.) * (1 - rec(!turn, t - i, score))
					);
			}
			if(t < 2+n-1) r = max(r, 1 - rec(!turn, 0, score));
		}
		return dp[turn][t][155 + score] = r;
	}
	double winProbability(vector <int> percentageA, vector <int> percentageB, vector <int> reboundA, vector <int> reboundB, int time, int scoreA, int scoreB) {
		p[0] = percentageA, p[1] = percentageB;
		b[0] = reboundA, b[1] = reboundB;
		s[0] = scoreA, s[1] = scoreB;
		n = percentageA.size();
		mset(dp, -1);
		return rec(false, time, 0);
	}
};