yukicoder No.352 カード並べ
351 が☆2 で 352 が☆3 なのか…(こっちのほうが考えやすかった)
解法
順番にカードを入れていき, そのたびかかるコストの期待値を求めていきます。
- カードが 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; }