Google Code Jam Japan 2011 A Final: アンテナ修復

GCJ

問題概要

配列Aが与えられる(長さL<=(small ? 5 : 1000))。適当に順序を入れ替えてΣA[i]*A[(i+1)%L]を最大化する問題。

考えたこと

  • 何か答えが小数で一瞬嫌な気がしたけど、すぐに最後に0.5*sin(2*PI/K)を掛ければよいことに気づいた。
  • この手のはどうせソートっぽいことをするはず。掛け算は値の差が大きいほど損するとかそんなの。
  • とはいえsmallはnext_permutationするだけなので流石にこれくらいならサクッと書けるので一応正解を持っておこう。
  • small正解後largeを考える。どうせ降順にソートするだけ。
  • smallで出した答えと合わない。冷静に考えれば一番でかい値と一番小さい値を掛けるとかもったいなさすぎる。
  • 左右に交互につけていけばいいのか。証明はしてないけど、直感的には明らか。実際small解とも一致した。
  • 提出。無事あってた。

本番中通ったコード

small用。O(N! * N)。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX_K = 1000;
double PI;

int K;
int Es[MAX_K];

double solve(){

	sort(Es, Es+K);

	int ans = 0;
	do{
		int tmp = 0;

		for(int i=0; i<K; i++){
			tmp += Es[i] * Es[(i+1)%K];
		}

		ans = max(ans, tmp);
	}while(next_permutation(Es, Es+K));

	return ans * 0.5 * sin(2*PI/K);
}

void initialize(){
	scanf("%d",&K);
	for(int i=0; i<K; i++){
		scanf("%d", Es+i);
	}
}

int main(){
	int T;
	PI = atan(1.0) * 4.0;
	scanf("%d",&T);

	for(int c=1; c<=T; c++){
		initialize();
		printf("Case #%d: %.10f\n", c, solve());
	}

	return 0;
}

large用。差分のみ。計算量O(N * log N)。

10a11
> int As[MAX_K];
14a16
> 	reverse(Es, Es+K);
16,18c18,21
< 	int ans = 0;
< 	do{
< 		int tmp = 0;
---
> 	int p = 0, q = K - 1;
> 	for(int i=0; i<K; i++){
> 		As[i%2==0 ? p++ : q--] = Es[i];
> 	}
20,25c23,26
< 		for(int i=0; i<K; i++){
< 			tmp += Es[i] * Es[(i+1)%K];
< 		}
< 
< 		ans = max(ans, tmp);
< 	}while(next_permutation(Es, Es+K));
---
> 	double ans = 0;
> 	for(int i=0; i<K; i++){
> 		ans += As[i] * As[(i+1)%K];
> 	}