SRM 463 500pt: Nisoku

TopCoder

問題概要

1.5<=x<=10.0の値が書かれたカードがN(<50)枚ある。このうち2枚を選んで和か積で置き換える。最後に残ったカードを最大化する問題。

考えたこと

  • (本番中は、ソートしてある区間の端っこ同士を足していくことまでは気付いたけど、どこまでの区間で足し算するかを全探索する発想がでなかった)
  • はじめてSystem Test Failedした問題なので記憶に残っている。
  • 今見返すと、入力がdoubleって珍しい。
  • x>=1.5という制限があるので、(x+y)*z >= x+y+zが成り立つ。つまり足し算は1回までしかしない。
  • よく使う知識の一つだけど、和が一定の時の積はバランスよく分割したほうが稼げる。
  • どこまでをバランスよく和に置き換えるかを全探索してやればよい。

practiceで通したコード

#include <vector>
#include <algorithm>
using namespace std;

struct Nisoku {

	double theMax(vector <double> cards) {
		const int N = cards.size();

		sort(cards.begin(), cards.end());

		double ret = 0.0;
		for(int add=0; add<=N; add+=2){
			double tmp = 1.0;
			for(int i=0; i<add-i-1; i++){
				tmp *= cards[i] + cards[add-i-1];
			}

			for(int i=add; i<N; i++){
				tmp *= cards[i];
			}

			ret = max(ret, tmp);
		}

		return ret;
	}

};