スポンサーサイト

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

Google Code Jam 2011 Qualification Round

2011/05/07 8:00 ~ 05/08 8:00 (JST)
Google Code Jam 2011 Qualification Round の参加記録。

去年の今頃は GCJ の存在を知らなかったので、今年が初参加。
丁寧に解説されているブログがたくさんあるので、ここでは、コンテスト中に考えたことを書いて、ソースコードを載せるだけにする。

Tags : プログラミング GCJ

結果

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

コンテスト中

朝、9:00 くらいから問題を読み始めた。
夜型の生活になっていて寝ていなかったので、やや眠い。

A. Bot Trust
読んだ。
読みにくい英語だなぁ。

入力サイズが小さいので、ふつうにシミュレーションすればよさそう。
がりがり
意外にめんどくさい。もう O(n2) でいいや。
書きあがった。
small submit. AC.
large submit.

B. Magicka
マギカ
英文長い。読みたくない...

ゆっくり読んだ。
これもシミュレーションするだけっぽい。
がりがり
書きあがった。
リストにある文字のヒストグラムを作って、oppose できるかの判定を少し速くした。多分しなくても通るけど。
submit.
ここまでで 2h + α くらいかかった。

C. Candy Splitting
読んだ。
おもしろそうな問題。すぐには解法が浮かばない。

わからん。ぐだぐだ。

アメの個数の総和を二進数で書いてみる。
1 が立っているビットがあれば、それは xor で二等分にできないからだめだよなー
あ、じゃあ全部 0 のときだけ分けられるのか。
最適な分け方は?
どう分けても許容解になるっぽい。 a xor b xor b = a とかを使えば示せる気がする。
それなら、大きいほうから目いっぱい兄が取ればいい。
submit.
ここまでで 3.5h くらい。

D. GoroSort
問題文が読めない。

眠くなったので中断して眠る。


21:30 くらい。
問題文読解に再挑戦。

わかった。
問題設定が意味不明だけど。
腕が 4 本ある Goro が机をばんばんやってソートする。
何ヶ月か前にやった CodeChef の BOGOSORT に似てる。あれは漸化式を作ってまじめに計算する問題だった。

これは、単純に、揃っているものは押さえて、揃ってないやつだけでシャッフルすればいいのでは?
それなら、期待値の漸化式も簡単に出せ...ない。
係数が求められない。
n 個の数からなる順列で、ちょうど k 個が正しい場所にあるものの個数。
閃かなかったので、この方針は保留。
別ルートで考えることにする。

サンプルを見る。
2 個ずつソートしてるだと!!
その方法のほうがよくなることはあるのかな。
あるかもしれない。
適当な部分集合で、それ自身で小さな順列になってるときはそこだけを先にソートするのがいいのかも。
でもそうなると、簡単には計算できそうにない。

とりあえず、揃ってないやつは一気にシャッフルする方針でサンプルを手計算してみる。
2 つずつのときと答えが一致した。
これはもしやと思って、n = 4 のケースもがんばって書き下す。
期待値はジャスト 4 。

一般に、n 個をシャッフルするときの期待値が n になるようだ。
多分合ってるだろうということで、ためしに small を出してみると AC.
large も submit.

全部終わり。
今 22:15 くらい。

解答

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

A.
int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int n; scanf("%d ",&n);
pair<char,int> seq[100];
rep(i,n) scanf("%c%d ",&seq[i].first,&seq[i].second);

int t=0;
int b=1,o=1;
rep(i,n){
char c=seq[i].first;
int pos=seq[i].second;
if(c=='B'){
int dif=abs(pos-b)+1;
t+=dif;
b=pos;

int nexto=o;
for(int j=i+1;j<n;j++){
if(seq[j].first=='O'){ nexto=seq[j].second; break; }
}
if (o<nexto) o=min(o+dif,nexto);
else if(o>nexto) o=max(o-dif,nexto);
}
else{
int dif=abs(pos-o)+1;
t+=dif;
o=pos;

int nextb=b;
for(int j=i+1;j<n;j++){
if(seq[j].first=='B'){ nextb=seq[j].second; break; }
}
if (b<nextb) b=min(b+dif,nextb);
else if(b>nextb) b=max(b-dif,nextb);
}
}

printf("Case #%d: %d\n",T,t);
}

return 0;
}


B.
int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int nc; scanf("%d",&nc);
char com[128][128]={};
rep(i,nc){
char s[4]; scanf("%s",s);
com[s[0]][s[1]]=s[2];
com[s[1]][s[0]]=s[2];
}

int no; scanf("%d",&no);
bool opp[128][128]={};
rep(i,no){
char s[4]; scanf("%s",s);
opp[s[0]][s[1]]=true;
opp[s[1]][s[0]]=true;
}

int n; scanf("%d ",&n);
int cnt[128]={};
deque<char> dq;
rep(i,n){
char c=getchar();
if(!dq.empty() && com[dq.back()][c]){
c=com[dq.back()][c];
cnt[dq.back()]--;
dq.pop_back();
}
dq.push_back(c);
cnt[c]++;
for(int a='A';a<='Z';a++) if(opp[c][a] && cnt[a]>0) {
while(!dq.empty()) dq.pop_back();
fill(cnt+'A',cnt+'Z'+1,0);
break;
}
}

printf("Case #%d: [",T);
rep(i,dq.size()){
printf("%c",dq[i]);
if(i<dq.size()-1) printf(", ");
}
puts("]");
}

return 0;
}


C.
int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int n; scanf("%d",&n);
int sum=0,cmin=INF,XOR=0;
rep(i,n){
int c; scanf("%d",&c);
sum+=c;
cmin=min(cmin,c);
XOR^=c;
}
if(XOR!=0) printf("Case #%d: NO\n",T);
else printf("Case #%d: %d\n",T,sum-cmin);
}

return 0;
}


D.
int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int n; scanf("%d",&n);
int difcnt=0;
rep(i,n){
int a; scanf("%d",&a);
if(a!=i+1) difcnt++;
}
printf("Case #%d: %.9f\n",T,(double)difcnt);
}

return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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