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"; }