一番左はじのボールの、一つ右めがけて投げ続ければよい
ボールの座標が3,8,10ならば4に投げ続け、3が倒れたら9へ投げ続ける
ソートをするのでO(nlogn)
邪悪なコードになったが、どうやらO(2^n)のコードが簡単だとか
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <typeinfo> #include <queue> using namespace std; typedef long long ll; int n; static double dp[4][16]; static bool flag[4][16]; int x[16]; double solve(int f, int t) { if (flag[f][t]) return dp[f][t]; if (t >= n) return 0; if (t == n-1) return 3; if (t == n-2) { if (f) { return 3; } if (x[n-1] - x[n-2] > 2) { return 6; } else { return 4.5; } } double p = 0; int d = 0; switch (f) { case 0: p += solve(0, t+1); break; case 1: p += solve(0, t+2); break; case 2: p += solve(1, t+1); break; case 3: p += solve(0, t+3); break; } bool b = false; if (x[t+1] - x[t] == 1) b = true; switch (f) { case 0: if (b) { p += solve(1, t); } else { d++; } break; case 1: d++; break; case 2: p += solve(3, t); break; case 3: d++; break; } bool b1 = false, b2 = false; if (x[t+1] - x[t] == 2) b1 = true; if (x[t+2] - x[t] == 2) b2 = true; switch (f) { case 0: if (b1) { p += solve(1, t); } else if (b2) { p += solve(2, t); } else { d++; } break; case 1: if (b2) { p += solve(3, t); } else { d++; } break; case 2: d++; break; case 3: d++; break; } switch (d) { case 0: p /= 3; p += 1; break; case 1: p /= 2; p += 1.5; break; case 2: p += 3; } dp[f][t] = p; return p; } int main() { cin >> n; vector<int> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } sort(v.begin(), v.end()); for (int i = 0; i < n; i++) { x[i] = v[i]; } printf("%.10f\n", solve(0, 0)); return 0; }