SRM 463 div2 hard, div1 med: Nisoku

未だに Nisoku ってどういう意味かよくわかってないんですがどういう意味なんでしょう?

問題

TopCoder Statistics - Problem Statement

解法

入力される数が 1.5 以上なので, 大抵の場合 a+b とするより a*b としたほうが得な感じがします。
a <= b として, a は 1.5 以上なので, a+b と a*b が拮抗するのは, b = 3 の時です。で, 3 という数字は, 2 つの数字を足し算すれば必ずそれ以上の数が生成されるので, 最終的な計算結果が最大になる場合は, 計算の形としては, (a+b) * (c+d) * e * f のように, 足し算はたかだか 2 つの数の間でだけなされて, それらの数を掛け算することになります。 (a+b+c) * d * e * f のように 3 つの数の組み合わせで足し算するのは絶対損するということです。

後は, どのように足し算する数の組を選ぶかが問題です。a <= b <= c <= d とすると,
(a+d)*(b+c) >= (a+b)*(c+d)
(a+d)*(b+c) >= (a+c)*(b+d)
が成り立つので, 足し算する数の集合 S (S は偶数個の数からなる集合)を決めれば, (S で最も小さい数)+(S で最も大きい数), (S で 2 番目に小さい数)+(S で 2 番目に大きい数), ... のように足し算していけば良いことがわかります。

また, 集合 S について, a <= b <= c とした時, (a+b)*c >= (a+c)*b が成り立つので, 集合 S には, 全体の cards の中で小さい数が入るのが有利ということがわかります。

ということで, cards をソートして, 集合 S は区間 [0, 0), [0, 2), ... を調べて得られる数のうち, 最も結果が大きい物を答えとすれば良いです。

class Nisoku {
public:
    double theMax(vector <double> cards) {
        sort(cards.begin(), cards.end());
        int n = cards.size();
        double ret = 0;
        for (int i = 0; i <= n; i+=2) {
            double tmp = 1;
            for (int j = i; j < n; j++) tmp *= cards[j];
            for (int j = 0; j < i/2; j++) tmp *= cards[j]+cards[i-j-1];
            ret = max(ret, tmp);
        }
        return ret;
    }
};