Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2010-03-02

SRM463 500

| 00:59 | はてなブックマーク - SRM463 500 - cafelier@SRM

  • これが最適解になることが納得できた
class Nisoku { public:
   double theMax(vector <double> cards) 
   {
      sort(cards.begin(), cards.end());

      double ans = 0.0;
      for(int i=0; 2*i<=cards.size(); ++i)
         ans = max(ans,
            accumulate(cards.begin()+2*i, cards.end(),
               inner_product( cards.begin(), cards.begin()+i,
                              cards.rend()-2*i,
                              1.0, multiplies<double>(), plus<double>() ),
               multiplies<double>()
            )
         );
      return ans;
   }
};
  • 全部の値が正なので
    • (△*x)+□ < (△+□)*x
    • よって、まず足し算し終わった後で掛け算、という流れが最適。
  • 全部の値が1.5以上なので
    • x≧3 なら x*□>x+□ (ab≧a+b iff (a-1)(b-1)≧1 より)
    • よって、2個足し算したら3以上になることと合わせると、3個以上を足し合わせることはない。
  • ここまでの理由から、最適解は
    • (a+b)*(c+d)*...*(e+f)*g*h*...*y*z
    • という形をしている
  • 全部の値が正なので
    • x≦y なら (□+x)*y ≧ (□+y)*x
    • よって、足し算部の数達a,b,..,e,f ≦ 掛け算部の数達g,h,..,y,z
  • 足し算部の2ペア (a+b)*(c+d) だけ取り出して考えると
    • この式の値を最大にするには
    • 一般性を失わず a≦b,c,d と仮定すると、c,d≦b である
    • 要は最大値と最小値が必ず足されてる
    • 「周の長さが同じ長方形の面積は正方形に近いほど大きい」のと同じ
  • この関係が全ての足し算部のペアに対して成り立つためには、
    • 足し算部の数をsortしたらa[0],a[1],...,a[n]だったとすると
    • (a[0]+a[n])*(a[1]+a[n-1])*... みたいに最大と最小をgreedyにペアにしていかないといけない
    • (そうなってなければ最小と最大が入ってる2ペアを選んだらswapしないといけないのに反する)
  • どこからが足し算部に入ってどこからが掛け算部かは、全探索すればよい
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20100302
 | 

presented by cafelier/k.inaba under CC0