SRM463::Div1::500 Nisoku

偉い人のブログを参考にしながら書いてみた。
証明はあとで考える。

// #includeは省略

#define REP(i,e) for(int i=0;i<(int)(e);i++)
#define FOR(i,b,e) for(int i=(int)(b);i<(int)(e);i++)

using namespace std;

typedef vector<double> vdouble;

class Nisoku{
public:
	double theMax(vdouble &v){
		sort(ALL(v));

		double best = 1.0;
		REP(i,v.size()) best*=v[i];
		
		REP(i,v.size()) REP(j,i) if((i-j)&1){
			double ans = 1.0;
			REP(k,j)              ans*=v[k];
			FOR(k,i+1,v.size())   ans*=v[k];
			for(int b=j,e=i;b<e;) ans*=v[b++]+v[e--];
			best = max(best,ans);
		}
		
		return best;
	}
};

• コンテスト中は「2未満の数の中から大きいのと小さいのを選んでペアにしていく」とやってダメだった。
• 「ソートして全ての(偶数長の)区間に対して、そこから大きいのと小さいのを選んでペアにしていき、最適を取る」とすれば正解。

• 「3未満で切ろう→2未満で切ろう」って
  • どうせ3である根拠も2である根拠もないんだから、
  • どうせエセ回答で特攻をかけるなら「任意の切り方を全て考えて最適を選ぶ」という一般化はしておくべきだった。実際これで何故か通るらしい。

cafelier@SRM - SRM463