AOJ2363 Unequal Dice

問題
多面体サイコロがあり、幾つかの面は数字が書かれていない場合もある。
サイコロを振ったとき、数字が書かれていない面が表になった場合、数字の面になるまでサイコロを振る。
多面体サイコロは、数字が書かれている面に対して、その数字とその面の出る確率が決まっている。
T個の異なる多面体サイコロが与えられる。それらのサイコロの出た目の期待値のいずれかが、もう一つの多面体サイコロXの期待値を上回る(0.0000001より大きい)かどうか判定せよ。

解説
期待値の典型問題。
数字が書かれている場合まで振り続ける、をどう捉えるかを考える。期待値の値はを出た目の平均であって、期待値それ自体も出た目のようなものとして扱うことができる。
よって、期待値の式は、 というようになるので、
この方程式を解いて、Eの式を計算する。あとはEの式の通りにそれぞれのサイコロの出る目の期待値を計算して判定すれば良い。
期待値DPの問題で自己ループがある場合など、こういった計算の簡略化をすることがよくある。

vector<pair<int, double>> dices[10];
double hanchoE;
int ns[10], ms[10];
int t;
 
bool solve() {
  rep(i, t) {
    double E = 0.0;
    double sumr = 0.0;
    rep(k, ms[i]) {
      E += dices[i][k].first * dices[i][k].second;
      sumr += dices[i][k].second;
    }
    E /= sumr;
    if(E > hanchoE + 0.0000001) {
      return true;
    }
  }
  return false;
}
 
int main() {
 
  cin >> t;
  rep(ii, t) {
    cin >> ns[ii] >> ms[ii];
    rep(i, ms[ii]) {
      int v; double r; cin >> v >> r;
      dices[ii].emplace_back(v, r);
    }
  }
 
  int p, q; cin >> p >> q;
  double sumr = 0.0;
  rep(i, q) {
    int v; double r; cin >> v >> r;
    hanchoE += v * r;
    sumr += r;
  }
 
  hanchoE /= sumr;
  cout << (solve() ? "YES" : "NO") << endl;
   
  return 0;
}