スポンサーサイト

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

CodeChef October Cook-Off

2011/10/24 01:00 ~ 03:30 (JST)
CodeChef October Cook-Off の参加記録

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

結果

A. AC (00:49:38)
B. -
C. 5TLE
D. -
E. AC (00:34:21)
Standing : 23/更新待ち
Rank (Short) : 39 → 32
Rating (Short) : 1490.446 → 1518.654


問題

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

A. Generalized Arithmetic Progression Free Sequence

次の規則で生成される数列 (x_k) を第 n 項まで求めよ。
x_1 = 1
k ≧ 2 について
x_k = ( 次の 2 条件をみたす最小の正整数 )
・ x_k > x_{k-1}
・ すべての i, j (i < k, i < j) について x_k ≠ a・x_i - b・x_j

1 ≦ a, b ≦ 50
1 ≦ n ≦ 1000

C. First non-Palindrome

アルファベット小文字のみからなる長さ N の文字列 S が与えられる。

整数 L ( 1 ≦ L ≦ N ) に対して、
K(L) := ( S[i] を左端とする S の長さ L の部分文字列が回文でないような最小の i )
( i は 1-indexed )
と定める。
ただし、長さ L のすべての部分文字列が回文になるときは K(L) = 0 と約束する。

100007N-1・K(1) + 100007N-2・K(2) + ... + 100007・K(N-1) + K(N)
を mod 264 で求めよ。

1 ≦ N ≦ 105

E. Chef Travel Routes

N 個の都市がある。
各都市間の接続関係を表したグラフと、T 個のツアーが与えられる。
各ツアーが、同じ都市を高々 1 回しか通らない、矛盾がないものかどうかを判定せよ。
矛盾がない場合は、ツアーで移動する合計距離を求めよ。

1 ≦ N, T ≦ 50

解答

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

A.
int main(){
int T; scanf("%d",&T);
while(T--){
int a,b,n; scanf("%d%d%d",&a,&b,&n);

int x[1000]={1};
static bool used[1000000];
rep(i,1000000) used[i]=false;
rep(k,n-1){
rep(i,k+1){
if(a*x[k]-b*x[i]>=0) used[a*x[k]-b*x[i]]=true;
if(a*x[i]-b*x[k]>=0) used[a*x[i]-b*x[k]]=true;
}

int y;
for(y=x[k]+1;used[y];y++);
x[k+1]=y;
}

rep(k,n) printf("%d%c",x[k],k<n-1?' ':'\n');
}

return 0;
}

x_1 から順番に作っていく。
絶対に使えない数にはチェックを入れていって、一度なめるだけで x_k が求められるようにする。

チェックがつく数は高々 O(n2) 個だから、合計の計算量は
O(n2 + n2) = O(n2)
となる。

C. ( あとで解いた )
char s[100001];
int len,rad[200000];

void Manacher(){
int n=2*len;
for(int i=0,j=0;i<n;){
while(0<=i-j && i+j+1<n && s[(i-j)/2]==s[(i+j+1)/2]) j++;
rad[i]=j;

int k;
for(k=1;i-k>=0 && rad[i-k]<rad[i]-k;k++) rad[i+k]=rad[i-k];

i+=k;
j=(j>k?j-k:0);
}
}

int next[200002],color[200002];

void init(){
rep(i,2*len+2){
next[i]=i;
color[i]=-1;
}
}

void gao(int l,int r,int c){
if(l>r) return;
if(next[l]==l){
gao(l+2,r,c);
color[l]=c;
next[l]=next[l+2];
}
else{
gao(next[l],r,c);
next[l]=next[next[l]];
}
}

int main(){
int T; scanf("%d ",&T);
while(T--){
gets(s);
len=strlen(s);

Manacher();

init();
rep(i,2*len-1){
int L=rad[i]+2;
int R=2*min((i+1)/2,len-i/2-1)+(i+1)%2;

gao(L,R,i);
}

for(int i=1;i<=len;i++){
if(~color[i]){
color[i]=color[i]/2-(i-1)/2;
}
color[i]++;
}

ull ans=0;
for(int i=1;i<=len;i++) ans=ans*100007+color[i];
printf("%llu\n",ans);
}

return 0;
}

まず、Manacher のアルゴリズムを使って、すべての位置を中心とする最長回文の半径を求める。
O(N) でできる。

あとは、左にある回文を優先的に、 Greedy に K(L) の値を割り当てればいい。
Union-Find の経路圧縮アルゴリズムのようなことをすれば、計算量は O(N+N) くらいになる。

なお、mod 264 というのは、unsigned long long で計算すれば勝手にそうなる。
( Java だと BigInteger を使わざるを得なくてめんどうだと聞いた。 )

難しい問題だけど、必要な知識はそろっていた。
( ちょうど、少し前に復習した問題の類題だった )

コンテスト中は、経路圧縮のコードにバグがあって、O(n2) になってしまっていた。
もうちょっとで解けていただけにとても悔しい。

E.
int main(){
int n; cin>>n;
map<string,int> f;
rep(i,n){
string s; cin>>s;
f[s]=i;
}

int d[50][50]={};

int m; cin>>m;
rep(i,m){
string s,t;
int D; cin>>s>>t>>D;
d[f[s]][f[t]]=D;
}

int T; cin>>T;
while(T--){
int k,ans=0,u,v; cin>>k;
bool vis[50]={};
rep(i,k){
string s; cin>>s;
if(ans==-1) continue;
if(f.count(s)==0){ ans=-1; continue; }

v=f[s];
if(i>0){
if(vis[v] || d[u][v]==0){ ans=-1; continue; }
ans+=d[u][v];
}
u=v;
vis[u]=true;
}
if(~ans) cout<<ans<<endl;
else cout<<"ERROR"<<endl;
}

return 0;
}

問題文にしたがって書く。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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