Insurance
問題
提出
解けた
以下、解法を書く。
三分探索と累積和を組み合わせて解いた。
最小にしたい関数は、失う金額の期待値なので、以下のようになる。
$$
\begin{align}
E(x) &=& \frac{1}{N}\sum_{i=1}^N (x+A_i-min(A_i,2x))\\
&=& \frac{1}{N}(\sum_{i=1}^N x+\sum_{i=1}^NA_i-\sum_{i=1}^Nmin(A_i,2x))\\
&=& \frac{1}{N}(N*x+\sum_{i=1}^NA_i-\sum_{i=1}^Nmin(A_i,2x))\\
\end{align}
$$
2項目はAiの和を計算していれば、$O(1)$で計算できる。
3項目は累積和を計算していれば、$O(1)$で計算できる。
3項目の和は、$2x$または$A_i$の小さい方を選んで和をとる。
つまり、$A_i$が$2x$以上の場合全て$2x$になる。
$A_i$の中で$2x$より小さいものの数を$k$とすると、3項目は以下のように書ける。
$$
\sum_{i}^{A_i<2x}A_i+(n-k)*2x
$$
この式の1項目は、$A_i$を昇順にソートして累積和をとることにより、前処理の計算量$O(N)$、算出時の計算量$O(1)$で求まる。
この関数E(x)の最小値を見つけるために、3分探索を行う。
3分探索の計算量は$O(log(max(A_i)/\epsilon))$となる。$\epsilon$は計算誤差で、今回の場合は$10^{-6}$になる。
よって、計算量は$O(N)$になるので、計算が間に合う。
以下、解説を見て思ったこと
3分探索の計算量を見積もっておらず、累積和を使ったが、累積和を使わないときの計算量は$O(Nlog(max(A_i)/\epsilon))$となるので、これでも間に合う。
また、答えとなり得る$x$は$A_i/2$のうちのどれかになるので、これを全て探索するという手も使える。
コメント