スポンサーサイト

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

Google Code Jam 2011 Round2

2011/06/04 23:00 ~ 25:30 (JST)
Google Code Jam 2011 Round2 の参加記録

上位 500 人が通過。
上位 1000 人が T シャツ。

Tags : プログラミング GCJ 未解決

結果

A. small: AC, large: AC
B. small: AC, large: --
C. small: WA, large: --
D. small: --, large: --

1199 / 3000 位

コンテスト中

A. Airport Walkways
読んだ。
やっぱり GCJ は問題文が微妙に読みにくい。

これは、どこで走っても結果は同じとかじゃないか??

いや、そんなことはない。
走っていい距離じゃなくて、走っていい時間が与えられるのか。

紙の上で x-t グラフとか数式とかを雑に書いてみる。
なぜか (思考が) バグって、結構な時間ぐだぐだしてしまった。体感では 20 ~ 30 分くらい。

えーと、、、
サンプルからも分かるように、遅いところを走ったほうが効率がいい。
なぜかというと、
区間 [i,i+1] を通るときの速度を v(i) とすると、答えは
Σi=1→X 1/v(i)
になる。
区間 [i,i+1] を走るということは 1/v(i) を小さくするということで、小さくなる度合いは v(i) が小さい (遅い) 方が大きいから。

なので、速度が遅いところを優先的に走ればいい。
Greedy.
X ≦ 106 なので、通路全体をナイーブに配列で持っても大丈夫。

ここまで分かっても、まだ思考が完全に整理できてなくて、なぜか実装に priority_queue を使ってしまった。
コードはすぐに書き上がった。
small submit.
correct.

計算量的には large も間に合うはずと思って、large もダウンロード。
しかし遅い。 ( それでも 2, 3 分くらい待ったら終わったんだろうけど、進捗状況を端末に表示してなかったのでわからなかった
提出〆切まであと 7 分くらいあったので、急いでボトルネックを割り出しにかかる。
どうやら priority_queue が遅いらしい。
log オーダーとはいえ、さすがに 106 個も要素が積まれれば無視できないか。
sort に書き換え。 ( sort 自体は nlogn だけど、本処理の log が消える。
この時点であと 3 分くらい。
small の答えが一致していることを確認。
large を走らせてみる。
サクサク動く!!
残り 1 分くらいで submit.
ここの時点で 1300 位くらい。ひどい。

結局、small だけに対応できる解法が分からなかった。

B. Spinning Blade

読んだ。
あんまり好みじゃない感じの問題。
とりあえず、small は 5 乗オーダーの全探索でいけそうなのでそれを書いてみよう。
書く。
バグる。
バグる。
入力がスペースで区切られてないとか、悪質すぎる。
バグる。
バグる。
ただの重心の計算がなぜかできない。色々とひどい。
やっと書きあがったときにはすでに満身創痍。
small submit. correct.

さて、B large に進むか C small に進むか。
B large はちょっと考えたくらいでは分からない気がしたし、何より好きな問題じゃなかったので C small に進むことにした。
今、1200 位くらい。

C. Expensive Dinner

読んだ。
好きなタイプの問題!!

あれ?
サンプルが何でそうなるのか分からない。
悶々
Explanation を丁寧に読み直す。
なるほど、
ウェイターを呼んで料理を注文して、それで別の人が条件を満たさなくなっても、あらためてウェイターを呼ばなくていいのか。
それだと、要するに、入店した順番に LCM をとっていくことになる。

このあたりから、コンテストの終了時刻がせまってきて、焦っている。

呼ぶ回数最小は 1, 2, 3, .., N の昇順、最大は N, N-1, .., 1 の降順でいいんじゃないかなー ( 違う
サンプルもそれで合うし。
書いてみよう。
書いた。
small submit.
incorrect.

fmm..
ここで時間切れ。

解説読んどこう。

解答

言語は C++。テンプレはここを参照。

A.
int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int len,walk,run,n;
double t_run;
scanf("%d%d%d%lf%d",&len,&walk,&run,&t_run,&n);

static int w[1000000];
rep(x,len) w[x]=0;
rep(i,n){
int a,b,w0; scanf("%d%d%d",&a,&b,&w0);
for(int x=a;x<b;x++) w[x]=w0;
}

sort(w,w+len);

double ans=0;
rep(x,len){
if(t_run*(w[x]+run)>1){
ans+=1.0/(w[x]+run);
t_run-=1.0/(w[x]+run);
}
else{
double dist=t_run*(w[x]+run);
ans+=t_run+(1-dist)/(w[x]+walk);
t_run=0;
}
}
printf("Case #%d: %.9f\n",T,ans);
}

return 0;
}


B. (small)
int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int r,c; scanf("%d%d%*d ",&r,&c);
static int w[500][500];
rep(y,r){
rep(x,c) w[y][x]=getchar()-'0';
getchar();
}

int k;
for(k=min(r,c);k>=3;k--){
rep(i,r-k+1) rep(j,c-k+1) {
double cy=i+(k-1.0)/2,cx=j+(k-1.0)/2,gy=0,gx=0;
for(int y=i;y<i+k;y++) for(int x=j;x<j+k;x++) {
if((y==i && x==j) || (y==i && x==j+k-1)
|| (y==i+k-1 && x==j) || (y==i+k-1 && x==j+k-1)) continue;
gy+=w[y][x]*(y-cy);
gx+=w[y][x]*(x-cx);
}
if(abs(gy)<EPS && abs(gx)<EPS) goto FOUND;
}
}
FOUND:;

if(k<3) printf("Case #%d: IMPOSSIBLE\n",T);
else printf("Case #%d: %d\n",T,k);
}

return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。