Google Code Jam Japan 2011 本戦 A. アンテナ修復

先日行われた本戦は、Aで2WAも出したことで完全に動揺し、
Tシャツ圏内は入りそうだしと安心しきってC-Largeに挑んでいたところ、
気付いたらTシャツ圏外に、C-Largeも組み上がらず、という残念な結果でした。

解けたものから記事を残して、反省しておこうと思います。
まずは本戦で唯一通せたA問題から。

• -

A : アンテナ修復

• 与えられた数字を並び替えて E(0)E(1) + … + E(K-1)E(0) を最大化する問題

• a < b < c < d とする
  • このとき、ab + bc + cd + da > ac + cb + bd + da は容易に示せる
  • つまり、昇順列の中での入れ替えは無意味
  • 今回は循環なので、答えは E(0) < E(1) < … < E(k) > … > E(K-1) の形のどれか

• これはE(0)を最小の要素、E(k)を最大の要素として昇順列を2つ作ることになる
  • ここまで分かれば、あとはいわゆるさやかちゃん法でおｋ

以下は本番で出したコード。

#include <iostream>
#include <cmath>

using namespace std;

const double PI = acos(-1);

int main(){
    int TEST; cin >> TEST;
    int a[1000];
    static long long dp[1000][1000];
    for(int test=1;test<=TEST;test++){
        int K; cin >> K;
        for(int i=0;i<K;i++) cin >> a[i];
        sort(a, a+K);
        memset(dp, 0, sizeof(dp));
        dp[0][1] = a[0]*a[1];
        for(int i=2;i<K;i++){
            for(int j=0;j+1<i;j++){
                dp[i-1][i] = max(dp[i-1][i], dp[j][i-1] + a[j]*a[i]);
                dp[j][i]   = max(dp[j][i], dp[j][i-1] + a[i-1]*a[i]);
            }
        }
        double res = 0.0;
        for(int i=0;i+1<K;i++){
            res = max(res, 0.5*(dp[i][K-1]+a[i]*a[K-1])*sin(2.0/K*PI));
        }
        printf("Case #%d: %.9lf\n", test, res);
    }
}