スポンサーサイト

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

Facebook Hacker Cup 2013 Qualification Round

解説はすでにいろんな人がわかりやすいのを書いてくれているので、問題文と自分のコードだけ。

Tags : プログラミング FBHC
 
リンク

結果

A : AC
B : AC
C : -

問題

A. Beautiful strings
a~z に 1~26 の数字を割り当てる。同じ数字を複数のアルファベットに割り当てることはできない。
アルファベットのみからなる文字列 s が与えられるので、対応する数字の和を最大化せよ。
大文字小文字は区別しない。

2 ≦ |s| ≦ 500

B. Balanced Smileys
文字列 s が balanced かどうか判定せよ。
・ 空文字列は balanced
・ 'a', 'b', ..., 'z', ' ', ':' のみからなる文字列は balanced
・ 「'(' + balanced な文字列 + ')'」 は balanced
・ 「balanced な文字列 + balanced な文字列」 は balanced
・ ":)" は balanced
・ ":(" は balanced
・ 以上のルールで作れる文字列のみが balanced

1 ≦ |s| ≦ 100

C. Find the Min
長さ k の非負整数列 m[0...k-1] が与えられる。
この数列を次のように延長する。
m[i] := ( m[i-k...i-1] に現れない最小の非負整数 ), i ≧ k
m[n-1] を求めよ。

1 ≦ k ≦ 10^5
k < n ≦ 10^9

ソースコード

A. Beautiful strings
貪欲。O(|s|)。
#include<cctype>
#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int solve(){
char s[512]; gets(s);

int freq[128]={};
for(int i=0;s[i];i++) if(isalpha(s[i])) freq[tolower(s[i])]++;
sort(freq,freq+128);

int res=0,a=26;
for(int c=127;c>=0;c--) if(freq[c]>0) res+=freq[c]*(a--);
return res;
}

int main(){
int T,t; scanf("%d ",&T);
for(t=1;t<=T;t++) printf("Case #%d: %d\n",t,solve());
return 0;
}


B. Balanced Smileys
DP。O(|s|^3)。
#include<cstdio>
#include<cstring>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

char s[128];

int dp[128][128];
int dfs(int l,int r){
int &res=dp[l][r];
if(res!=-1) return res;

if(l==r) return res=1;

bool ok=true;
for(int i=l;i<r;i++) if('a'<=s[i] && s[i]<='z' || s[i]==' ' || s[i]==':'); else ok=false;
if(ok) return res=1;

if(s[l]=='(' && s[r-1]==')' && dfs(l+1,r-1)) return res=1;

for(int i=l+1;i<r;i++) if(dfs(l,i) && dfs(i,r)) return res=1;

if(r-l==2 && s[l]==':' && s[l+1]==')') return res=1;
if(r-l==2 && s[l]==':' && s[l+1]=='(') return res=1;

return res=0;
}

const char *solve(){
gets(s);
memset(dp,-1,sizeof dp);
return dfs(0,strlen(s))?"YES":"NO";
}

int main(){
int T,t; scanf("%d ",&T);
for(t=1;t<=T;t++) printf("Case #%d: %s\n",t,solve());
return 0;
}


C. Find the Min
priority queue でうまいことやる。O(k log k)。
#include<queue>
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

int solve(){
int n,k; scanf("%d%d",&n,&k);
static int a[100000];
{
int b,c,r; scanf("%d%d%d%d",a,&b,&c,&r);
rep(i,k-1) a[i+1]=((ll)b*a[i]+c)%r;
}

static int cnt[100001];
rep(i,k+1) cnt[i]=0;
rep(i,k) if(a[i]<=k) cnt[a[i]]++;

priority_queue<int> Q;
rep(i,k+1) if(cnt[i]==0) Q.push(-i);

vector<int> seq;
rep(i,k+1){
seq.push_back(-Q.top());
Q.pop();
if(i<k && a[i]<=k){
cnt[a[i]]--;
if(cnt[a[i]]==0) Q.push(-a[i]);
}
}
return seq[n%(k+1)];
}

int main(){
int T,t; scanf("%d",&T);
for(t=1;t<=T;t++) printf("Case #%d: %d\n",t,solve());
return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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