CODE FESTIVAL 2016 Grand Final,D: Dice Game

https://beta.atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_d

面白い。

petrが赤のサイコロを選ぶ確率をX,touristがiが出た時に赤という確率をxiとします。するとtouristが勝つ確率は
f(X,x1...x6)=1-X+Σ((pi+qi)X-qi)xiとなります。
touristはこの値を大きくしようとするので、(pi+qi)X-qi>=0ならxi=1,そうでないならxi=0とします。
petrはtouristがこの戦略をとった時にfが一番小さくなるようなXを選びます。
(pi+qi)X-qiの正負が変わるのはX=qi/(pi+qi)の時しかなく、fは一次式なので、X=0,1,qi/(pi+qi)だけ試せばよいです。

もうちょっとミニマックスを意識出来たらよかったかなぁ。

double P[10], Q[10];

double f(double a) {
	double ans = 1 - a;
	rep(i, 0, 6) {
		ans += max(0.0, (P[i] + Q[i]) * a - Q[i]);
	}
	return ans;
}

void solve() {
	rep(i, 0, 6) {
		int a; cin >> a;
		P[i] = a / 100.0;
	}
	rep(i, 0, 6) {
		int a; cin >> a;
		Q[i] = a / 100.0;
	}
	double ans = min(f(0), f(1));
	rep(i, 0, 6) {
		ans = min(ans, f(Q[i] / (P[i] + Q[i])));
	}
	cout << ans << "\n";
}