スポンサーサイト

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

CodeChef April Cook-Off Challenge

2011/04/25 1:00~3:30 (JST)
CodeChef の月 1 ショートコンテストの参加記録

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

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. 3WA
B. -
C. AC (00:35:57)
D. -
E. AC (00:45:44)
Standing : 59/297
Rank (Short) : 74 → 69
Rating (Short) : 1207.825 → 1231.803


問題

問題セットの原文はここを参照。

A. The Grand Cook Off
C (≦ 100) 人のシェフがいて、各々が 1 以上 100 以下のお金を持っている。
シェフの中から一様ランダムに 2 人選び、
・ 1 人がもう 1 人に持っているお金をすべて渡す
・ お金を渡したシェフは消える
という操作を、残りのシェフが 2 人になるまで繰り返す。
残った 2 人のシェフが持っているお金の差の期待値はいくらか?

B.

C. Internet Media Types
拡張子とメディアタイプの組が N (≦ 100) 個与えられる。
続いて Q (≦ 100) 個のファイル名が与えられるので、それぞれのファイルがどのメディアタイプに対応するかを答えよ。

D.

E. A Prime Conjecture
整数 N (61 < N < 106) が、素数 + 素数2 + 素数3 という形で書けるかどうかを判定せよ。
書ける場合は具体的例を 1 つ答えよ。

解答

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

A.


B.


C.
int main(){
int n,q; cin>>n>>q;
map<string,string> f;
rep(i,n){
string ext,media; cin>>ext>>media;
f[ext]=media;
}
rep(i,q){
string name; cin>>name;
size_t pos=name.find_last_of('.');
if(pos==string::npos) cout<<"unknown"<<endl;
else{
if(f.count(name.substr(pos+1))==0) cout<<"unknown"<<endl;
else cout<<f[name.substr(pos+1)]<<endl;
}
}

return 0;
}

連想配列を使ってやるだけ。
find_last_of を使うとファイル名から拡張子を取り出す処理が簡単に書ける。

D.


E.
int main(){
const int Ne=1000100;
static bool er[Ne]; er[0]=er[1]=true;
for(int i=2;i*i<Ne;i++) if(!er[i]) for(int j=i*i;j<Ne;j+=i) er[j]=true;
vi p; rep(i,Ne) if(!er[i]) p.pb(i);

vi p2,p3;
for(int i=0;p[i]*p[i]<1000000;i++) p2.pb(p[i]*p[i]);
for(int i=0;p[i]*p[i]*p[i]<1000000;i++) p3.pb(p[i]*p[i]*p[i]);

for(int n;scanf("%d",&n),n;){
rep(i,p3.size()){
if(n<p3[i]) break;
rep(j,p2.size()){
if(n<p3[i]+p2[j]) break;
int tmp=n-p3[i]-p2[j];
if(!er[tmp]){
printf("%d %d %d\n",tmp,p[j],p[i]);
goto FOUND;
}
}
}
puts("0 0 0");
FOUND:;
}

return 0;
}

基本的には全探索。
ただし、3乗, 2乗, 1乗の順で決めていって探索空間を狭くするという工夫をしないと TLE になるかもしれない。
3乗, 2乗についてはすべての場合を調べて、残る 1乗 = N - 3乗 - 2乗 が素数かどうかは、エラトステネスで篩ったときの配列を使えば O(1) で判定できる。

以前、AOJ でほとんど同じ問題を解いたような気もする。
たしか、ヤシガニなんとか。

感想

経験上、CodeChef Cook-Off は正答数が横並びになることが多い。( 難しい問題はほとんど誰も解けないので
そのときはかかった時間によって順位が決まるので、解ける問題を WA なしに解けたことはよかった。
submit する前にしっかり見直しもした。

簡単な C を解くのになぜ 30 分もかかったのかというと、最初、ずっと A を考えていたから。
貪欲に上位を狙うなら、適当なところで見切りをつけて、正解者が多い問題に切り替えるべきだった。

A は、今の自分には難しくて結局解けなかったけど、まったく手がつけられないほどではない。
やはり、当面の目標はこの難易度 (TopCoder Div1 Medium, Codeforces C~D レベル) がそこそこ解けるようになることか。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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