# ABC314 E - Roulettes

解法の正当性がやや不安です.

---

## 問題リンク
- https://atcoder.jp/contests/abc314/tasks/abc314_e

## 解法
数学的な計算のみでは答えは求まりそうないので, 期待値DPでうまくやります.

### DP
- $f(x):=$高橋君が最適な戦略をとったとき,スコアが$x$以上になるまでに必要なコストの期待値

とします.この時,以下が成り立ちます.

$$f(x)=\min_{i=1,2,\dots,N}{E_i}$$

ただし,
$$E_i=\frac{1}{P_i}{\sum_{j=1}^{P_i}}\left(C_i+f(x-S_{i,j})\right)$$

で $E_i$ は $i$ 番目のルーレットを選んだ時を選んだ時にかかるコストの期待値を表します.

$f$ の初期条件として,以下が成り立ちます.

- $x\leq 0$ に対して $f(x)=0$

あとはこの通りにメモ化再帰するとうまくいきそうです...

using ld = long double;
vector<ld> dp(m + 1, -1);  //
auto f = [&](const auto& f, int x) -> ld {
    if (x <= 0) return 0;
    if (dp[x] >= 0) return dp[x];
    dp[x] = infl;

    rep(i, n) {
        ld e = 0;                                                 // 期待値
        rep(j, p[i]) e += (ld)(c[i] + f(f, x - s[i][j])) / p[i];  // 遷移

        chmin(dp[x], e);
    }
    return dp[x];
};
cout << fixed << setprecision(12) << f(f, m) << '\n';

が実はそうでもありません.

### 問題点

これだとサンプル2には通りません.$S_{i,j}=0$ の時に壊れます.

$S_{i,j}=0$ の時,上の式のままだと$f(x)$ を求めるために$f(x)$の値を必要としますが,これはおかしいですね...

### 解消
こういう時,遷移の式をうまく整理(移項)することで解消できたりします.

今回もそれが使えます...が少しややこしいです.

$f(x)$ を求める際の遷移の式に注目します.

$f(x)=\min E$ なので $E_i$ が最小となるような $i$ をとります.この時,もちろん $f(x)=E_i$です.

$S_{i,j}=0$ であるような $j$ の個数を $z_i$ とすることで $E_i(=f(x))$ は次のように書けます.

$$E_i=f(x)=C_i+\frac{1}{P_i}\left(z_if(x)+\sum_{S_{i,j}\neq0}{f(x-S_{i,j})}\right)$$

したがって移項すると

$$\left(1-\frac{z_i}{P_i}\right)f(x)=C_i+\frac{1}{P_i}\sum_{S_{i,j}\neq0}f(x-S_{i,j})$$

となり,

$$f(x)=\frac{1}{P_i-z_i}\left(P_iC_i+\sum_{S_{i,j}\neq0}f(x-S_{i,j})\right)\cdots\bigstar$$

が得られます.

したがって, $E_i=f(x)$ となるような $i$ に対して $\bigstar$ が成り立ち,遷移が行えます.

実際に条件を満たすような $i$ を特定するのは無理そうですが,$i=1,2,\dots,N$ に対して $E_i=f(x)$ と仮定して $\bigstar$ により $f(x)$ を求めることにします.そうして求めた $f(x)$ うち,最小のものが正しい $f(x)$ です.

以上より計算量 $O(M\sum{P_i})$ で答えである $f(M)$ 求めることができます.

### 実装

int main() {
    int n, m;
    read(n, m);
    vector<int> c(n), p(n);
    vector<vector<int>> s(n);
    rep(i, n) {
        read(c[i], p[i]);
        rep(j, p[i]) {
            int a;
            read(a);
            s[i].emplace_back(a);
        }
    }
 
    vector<ld> dp(m + 1, -1);
    auto f = [&](const auto& f, int x) -> ld {
        if (x <= 0) return 0;
        if (dp[x] >= 0) return dp[x];
        dp[x] = infl;
 
        rep(i, n) {
            int zero = 0;
            ld sum = (ld)p[i] * c[i];
            rep(j, p[i]) {
                if (s[i][j]) {
                    sum += f(f, x - s[i][j]);
                } else {
                    ++zero;
                }
            }
            ld e = (ld)sum / (p[i] - zero);
            chmin(dp[x], e);
        }
        return dp[x];
    };
    cout << fixed << setprecision(12) << f(f, m) << '\n';
}

- https://atcoder.jp/contests/abc314/submissions/44553622