スポンサーサイト

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

Facebook Hacker Cup 2012 Qualification Round

2011/01/21 09:00 ~ 01/25 09:00 (JST)
Facebook Hacker Cup 2012 Qualification Round の参加記録

3 問中 1 問以上正解で通過

Tags : プログラミング FBHC

結果

A. AC
B. -
C. AC


B は reading hard らしい。
ノルマはクリアしていたので読んでいない。
公式解ではスライド RMQ を使うとか。

C はシステムのバグで submit に失敗して時間切れになったけど、あとで見たら submit したことになっていた。
よくわからん。

問題

問題セットの原文はここを参照。 ( Facebook でのログイン必須 )

A. Billboards

W × H の看板に文字列を印字する。
看板の左上から横書きで詰めていく。
文字列中の空白で改行することができる。
1 文字のサイズを最大でいくつにすることができるか?

文字と文字の間、行と行の間にスペースはできないものとする。

1 ≦ W, H ≦ 1000
文字列長 ≦ 1000

C. Alphabet Soup

与えられる文字列を使って "HACKERCUP" という文字列を何回作ることができるか?

解答

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

A.
bool isOK(const vector<int> &L,int sz,int w,int h){
int n=L.size();
int col=0,row=0;
rep(i,n){
if(L[i]*sz>w) return false;
if(i>0 && col+(1+L[i])*sz<=w){ // 今の行に追加
col+=(1+L[i])*sz;
}
else{ // 次の行にいく
col=L[i]*sz;
row+=sz;
}
}
return row<=h;
}

int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int w,h; scanf("%d%d ",&w,&h);
char s[1024]; gets(s);
vector<int> L;
for(int i=0,pre=0;;i++) if(s[i]==' ' || s[i]=='\0') {
L.push_back(i-pre);
pre=i+1;
if(!s[i]) break;
}

int lo=0,hi=1000;
while(lo<hi){
int mi=(lo+hi+1)/2;
if(isOK(L,mi,w,h)) lo=mi; else hi=mi-1;
}

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

return 0;
}

文字サイズで二分探索。
文字サイズを固定したとき、そのサイズで印字できるかどうかは前から敷き詰めていけば判定できる。
文字サイズ全探索でもたぶん間に合う。

C.
int main(){
int T0; scanf("%d ",&T0);
for(int T=1;T<=T0;T++){
char s[1024]; gets(s);
int freq[128]={};
for(int i=0;s[i];i++) freq[s[i]]++;

int ans=7777777;
ans=min(ans,freq['A']);
ans=min(ans,freq['C']/2);
ans=min(ans,freq['E']);
ans=min(ans,freq['H']);
ans=min(ans,freq['K']);
ans=min(ans,freq['P']);
ans=min(ans,freq['R']);
ans=min(ans,freq['U']);
printf("Case %d: %d\n",T,ans);
}

return 0;
}

KUPC A. KUPC
配列で counting.
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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