cafelier@SRM

SRM463 500

あとで | 00:59 |

• これが最適解になることが納得できた

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
• 足し算部の２ペア (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にペアにしていかないといけない
  • （そうなってなければ最小と最大が入ってる２ペアを選んだらswapしないといけないのに反する）
• どこからが足し算部に入ってどこからが掛け算部かは、全探索すればよい