yukicoder No.352 カード並べ

351 が☆2 で 352 が☆3 なのか…(こっちのほうが考えやすかった)

問題

No.352 カード並べ - yukicoder

解法

順番にカードを入れていき, そのたびかかるコストの期待値を求めていきます。

• カードが M 枚場に並んでいる場合, 端っこに置く確率は 2/(M+1) で
• 端以外に置く確率は (M-1)/(M+1) 両端に並んでいるカードは, M*(M-1)/2 通りありますが, それぞれは等確率で選ばれます。例えば, M=3 の場合, 1-2, 1-3, 2-3 というのがそれぞれ等確率で現れると考えて良いので, これらを全列挙して期待値を求めます。

以上を考慮すれば答えが得られます。

int main() {
    int N;
    cin >> N;
    double ans = 0;
    for (int i = 1; i <= N; i++) {
        if (i <= 2) ans += 1;
        else {
            double plus = 2./i;
            int sum = 0;
            for (int j = 1; j <= i-1; j++) for (int k = j+1; k <= i-1; k++) {
                sum += j*k;
            }
            plus += 2.*sum/i/(i-1);
            ans += plus;
        }
    }
    printf("%.10lf\n", ans);
    return 0;
}