SRM 463 Div2 Hard Nisoku

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10760&rd=14148

N枚のカードがあり、各カードには1.5から10.0までの数字が書かれている。このうちから2枚選んで取り出してカードに書いてある数字を足した数かかけた数を新しいカードに書いてそのカードをカードの山に戻す。選んだカードは捨てる。これをカードが残り1枚になるまで繰り返す。残ったカードに書いてある数字を最大化せよ。

やりかた

解説を参考にしました。

数字が1.5以上なので(x + y) * z >= x + y + zが成立する。なので3枚のカード以上を足しあわせることはない。足し算のほうが大きくなるのは数字が小さい時に限られるのでまずソートする。小さい方から何番目（図におけるi）までを足し算するカードなのか決めたら、そこまでは大きい方と小さい方を足し算する。なぜそのように足すのかというと、例えばa,b,c,dという数字(a < b < c < d)を足す組を考える時、最終的にかけた結果が最大になるのは(a + d) * (b + c)である。つまり足した組がなるべく近い数字になればそれを掛けあわせた時に結果が最も大きくなりうるのである。i番目以降は普通に掛け算する。これをiを動かして全て調べればいい。

class Nisoku {
public:
  double theMax(vector <double> cards) {
    double result = 0.0;
    int N = cards.size();
    sort(ALL(cards));

    for(int i = 0; i <= N; i += 2){
      double tmp = 1.0;
      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]);

      result = max(result, tmp);
    }
    return result;
  }
};

そういうことか。
最近のDiv2 Medium / Div1 Easy の難度ではないだろか。

SRM462はわけわからなかったので一旦飛ばす。