スポンサーサイト

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

Google Code Jam Japan 2011 予選

2011/10/01 13:00 ~ 19:00 (JST)
Google Code Jam Japan 2011 予選の参加記録

基本的なルールは GCJ と一緒。
1 つ以上の問題について Small と Large を解けば通過。

Tags : プログラミング GCJJ

結果

A. small: WA, AC (1:00:21)
A. large: AC (1:01:00)
B. small: AC (2:00:34)
B. large: AC (3:33:13)
C. small: AC (1:18:51)
C. large: AC (1:19:35)

88 / 918(?) 位

コンテスト中

コンテスト中に考えたことなどを書く。
問題はここから見ることができる。

A. カードシャッフル

シミュレーション。

真っ先に思いつくのは、作業用配列を用意して、1 枚ずつシャッフルする方法。
シャッフル 1 回につき O(M) かかるので、もちろんダメ。

次に思いつくのは、カードの束を 1 つの区間と見てまとめて処理する方法。
がんばれば書けるけど、複雑になるからできるだけやりたくない。
「GCJ なんだからきっとシンプルな解法があるはず」 と思って、すぐにコーディングに移らずにもうちょっと考える。
:
:
逆からやっていけば簡単?
知りたいのは 1 枚だけだから、逆順にシャッフルしていけば動かすカードは 1 枚でいい。
( 順方向のシャッフルでこれができないのは、知りたいカードが最初どの位置にあるか分からないから )

実装軽そう。
書く。書く。書く。バグバグバグバグ...
書きあがった。
submit.
incorrect.
直す。
submit.
correct!
large も出す。

正解数が多い C へ。

C. ビット数

ぱっと見て方針が立たないのでサンプルを書き下してみる。

二進数の筆算の要領で下の桁から見ていく。
・ N の i 桁目が 0 なら a の i 桁目 = 1, b の i 桁目 = 1 にして、N の上の桁から 1 つもらってくる
・ N の i 桁目が 1 から a の i 桁目 = 0, b の i 桁目 = 1 (逆でもいい)
とすればいけそう?
計算量は O(log N).

これで最適解が得られることの証明はできなかったけど、small は何回でも出せるので、とりあえず書いて出してしまう。 ← 罪!!
correct.
large も出す。

B. 最高のコーヒー

難しい。

すぐに思いつくのは、コーヒーは賞味期限が早い順に飲むとしていい、ということ。
これはいつかの SRM Div.1 500 とか UTPC 2011 First Acceptance とかで散々見たのでさすがに気付いた。
でもそこから進まない。

全然わからないのでぐだぐだしてしまう。

ずいぶん時間が経ってから、とりあえず全探索で small だけでも出すことにした。
書く。
submit.
correct.

ずっと考えていると、別の方針が浮かんだ。

満足度最大のコーヒーは絶対に飲むべき。
また、飲むならできるだけ賞味期限に近い日に飲むのがよい。

満足度最大のコーヒーを飲んだら、残っている日の中で、満足度が 2 番目に高いコーヒーを飲めばいい。
以下同様。

つまり、満足度の降順でソートして、区間のできるだけ後ろから割り当てていくことを繰り返せばいい。
1 つのコーヒーを飲む日付が複数の区間にまたがることがあるので、そこは気合で何とかする。

実装が難しいけど、アイデアは正しいと確信できたからがんばって書く。
がりがり。
書いた。
small の出力と diff を取ってみる。あってそうなので large submit.

全部出した。終了。

終わってから

全部正解だった。
A と C は想定解どおりだった。
B は想定解の方が若干シンプルだったけど、どちらにせよ実装は難しめ。
C はさらにシンプルな解法があった。

みんなが B を難なく提出していてレベルの差を感じる。 ( 少なくともそのように見えた )

C の解法の証明に関しては、公式の解説が非常にスマート。

解答

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

A.
int main(){
int T0; scanf("%d",&T0);
rep(T,T0){
int m,c,w; scanf("%d%d%d",&m,&c,&w); w--;
int a[100],b[100];
rep(i,c) scanf("%d%d",a+i,b+i), a[i]--;

for(int i=c-1;i>=0;i--){
if (w<b[i]) w+=a[i];
else if(w<b[i]+a[i]) w-=b[i];
}

printf("Case #%d: %d\n",T+1,w+1);
}

return 0;
}


B.
struct Coffee{
int s;
ll c,t;
bool operator<(const Coffee &C)const{ return s>C.s; }
};

struct Interval{
ll a,b;
Interval(ll A,ll B):a(A),b(B){}
bool operator<(const Interval &I)const{ return a<I.a; }
};

int main(){
int T0; scanf("%d",&T0);
rep(T,T0){
int n;
ll k; scanf("%d%lld",&n,&k);
Coffee C[100];
rep(i,n){
scanf("%lld%lld%d",&C[i].c,&C[i].t,&C[i].s);
C[i].c=min(C[i].c,C[i].t);
}

sort(C,C+n);

ll ans=0;
vector<Interval> I;
I.push_back(Interval(-1,0)); // sentinel
rep(i,n){
while(1){
int j;
ll t=C[i].t;
for(j=I.size()-1;j>=0;j--){
if(I[j].b<t) break;
t=min(t,I[j].a);
}
if(j==-1 || C[i].c==0) break;

ll left=max(I[j].b,t-C[i].c);
I.push_back(Interval(left,t));
sort(I.begin(),I.end());

C[i].c-=t-left;
ans+=C[i].s*(t-left);
}
}
printf("Case #%d: %lld\n",T+1,ans);
}

return 0;
}


C.
int main(){
int T0; scanf("%d",&T0);
rep(T,T0){
ll n; scanf("%lld",&n);
int ans=0;
for(ll b=1;n>0;b*=2){
if(n&b){
ans++;
n-=b;
}
else{
ans+=2;
n-=2*b;
}
}
printf("Case #%d: %d\n",T+1,ans);
}

return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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