Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2049-a6984b38
この記事にトラックバックする(FC2ブログユーザー)

Japan 2011 決勝 A問題 - アンテナ修復 (この記事を編集する[管理者用])

Source

Google Code Jam Japan 2011 決勝 A問題

問題概要

問題分が日本語なので略.

解法

三角形の面積は,2辺の長さとsin(間の角)と1/2の積なので,
与えられた要素を並び替えて,隣り合う積の和を最大化すればいい.(最初と最後は隣り合うとみなして)
直感的に大きいものは大きいものと当てたほうがいいから,一番大きい物を起点に,その左右に1個ずつならべていく.
少なくても,2要素をswapしてこれ以上大きくできないのは自明で,これが最大値なのもちゃんと証明すれば証明できる.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define EPS 1e-10
void doubleSort(double d[],int s){int i,j;double k1,k2,t;if(s<=1)return;k1=(d[0]+d[s-1])/2.0;k2=k1+EPS;k1-=EPS;i=-1;j=s;for(;;){while(d[++i]<k1);while(d[--j]>k2);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}doubleSort(d,i);doubleSort(d+j+1,s-j-1);}

int main(){
  int i,j,k,l,m,n;
  int size, count=0;
  double in[2000], arr[2000], res, sn, pi;
  int st, ed;

  pi = acos(0)*2;

  scanf("%d",&size);
  while(size--){
/*    fprintf(stderr,"size %d\n",size);*/

    scanf("%d",&n);
    rep(i,n) scanf("%lf",in+i);
    doubleSort(in,n);

    st = 0; ed = n-1;
    rep(i,n){
      if(i%2==0) arr[st++] = in[i];
      else       arr[ed--] = in[i];
    }

    res = 0;
    sn = sin(2*pi / n) / 2;
    rep(i,n) res += arr[i]*arr[(i+1)%n];
    res *= sn;

    printf("Case #%d: %.10lf\n",++count,res);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2049-a6984b38
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。