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