CodeChef September Cook (2012)
ハッキングされて、少し重くなっていたとのことでしたが、普段自分の端末が遅い場合が多いので気にせず参加しました。CodeChefが重いのか、e-mobileが重いのか、わからずじまいです。
数分たってから、解いた人が見える問題を解きました。問題はこちら。
Carvans：前から順に数えるだけです。「現在の速度」を記録しておいて、それ以下の速度の車があればそれをカウントし、「現在の速度」を更新します。
Recipe Reconstruction:文字列を前後両方からペアで見ていきます。もしも回文になっていなければ数を0倍、両方が?ならば26倍、他の場合は1倍すればOKです。文字数が奇数の場合、真ん中の文字が?ならば更に26倍する必要があります。
Ratingが上がりました。1316->1577です(小数点以下四捨五入)。
Codeforces Round #140 (Div.2)
Round #133以来の参加で、ひさしぶりだったのが災いしたか、今ひとつでした。Eは解けなかったのですが、それっぽいアルゴリズムを導出したので、備忘録として書いておきます。問題はこちら。
A:ベクトルの変化を考えるだけの問題なのですが、何故か手こずりました。落ち着いて計算しないといけません。まっすぐ行ってるかどうかは傾きを比較すればよいだけです。左右の判定が少し面倒で、A-B間のベクトルを90度回転させた時、その回転させたベクトルとB-C間のベクトルとの符号を比べなければなりませんでした。それでも未だどこかミスがあるようです(^^;
B:与えられる1-nの並び替え配列に対し、前側から線形探索した場合と後側から線形探索した場合のどちらが速くなるかを考える問題です。単純にリニアサーチすると当然間に合いませんので、格納方法を逆引きにしてやります。つまり、配列a[i]は、数字iが何番目に入っているか、を示すものとします。後は、前側からならa[i]回、後側からならn-a[i]+1回という計算をするだけです。
C:ハノイの塔です。ただし、通常のハノイの塔と違うのは「隣の塔にしか移動できない」という事です。漸化式を立ててとけば、求めるべき値が3^n-1という事になりますから、繰り返し二乗法を用いれば終わりです。
E:フィボナッチ数F_nに対して、gcd(F_n,F_m)=F_(gcd(n,m))が成立します。これは一般化可能で、k個のフィボナッチ数に対し、その最大公約数はその添字の最大公約数Gに対し、F_Gにより与えられます。ここで、Gの条件として区間[l,r]中にk個以上Gの倍数がなければなりません。これを逆に考えると、G=r/k-l/kにより求められます(演算はintで考えてください)。後は求めたGに対してフィボナッチ数を計算すれば良い…筈なのですが、残り時間ではフィボナッチ数の高速計算は書けず(行列の繰り返し二乗法ぐらいライブラリ化しておけばよかったのですが)、時間不足で解けませんでした。
結果：xox--でした。
[Carvans,AC]
#include<stdio.h>
int main(void){
unsigned t,n,i,now,count,input;
scanf("%u",&t);
while(t--){
scanf("%u",&n);
scanf("%u",&now);
count=1;
for(i=0;i<n-1;i++){
scanf("%u",&input);
if(input<=now) count++,now=input;
}
printf("%u\n",count);
}
return 0;
}
[Recipe Reconstruction,AC]
#include<stdio.h>
#include<string.h>
int main(void){
int t,l,i,tmp,bools;
unsigned int num;
const unsigned int mod=10000009;
char str[1000005];
scanf("%d%*c",&t);
while(t--){
scanf("%1000000s%*c",str);
tmp=(l=strlen(str))/2;
num=1;
for(i=0;i<tmp;i++){
bools=(str[i]=='\?')+(str[l-1-i]=='\?');
switch(bools){
case 2:
num*=26;
break;
case 1:
num*=1;
break;
case 0:
num*=(str[i]==str[l-1-i]);
break;
}
num%=mod;
}
if(l%2 && str[tmp]=='\?') num*=26;
num%=mod;
printf("%u\n",num);
}
return 0;
}
Codeforces Round #140 (Div.2)
[A:Where do I Turn?,WA]
#include<stdio.h>
int main(void){
struct point{
int x;
int y;
}a,b,c,dif[2];
scanf("%d %d",&a.x,&a.y);
scanf("%d %d",&b.x,&b.y);
scanf("%d %d",&c.x,&c.y);
dif[0].x=b.x-a.x;
dif[0].y=b.y-a.y;
dif[1].x=c.x-b.x;
dif[1].y=c.y-b.y;
if(dif[0].x*dif[1].y==dif[1].x*dif[0].y) puts("TOWARDS");
else{
if(dif[0].y*dif[1].x<0 && dif[0].x*dif[1].y>0) puts("LEFT");
else if(dif[0].y*dif[1].x<0 && dif[0].x==0 && dif [1].y==0) puts("LEFT");
else if(dif[0].x*dif[1].y>0 && dif[0].y==0 && dif [1].x==0) puts("LEFT");
else puts("RIGHT");
}
return 0;
}
[B:Effective Approach,AC]
#include<stdio.h>
int main(void){
int array[(int)1E5+1];
int i,j,k,n,m;
unsigned long long front,rear;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&k);
array[k]=i+1;
}
scanf("%d",&m);
front=rear=0;
for(i=0;i<m;i++){
scanf("%d",&k);
front+=array[k];
rear+=n-array[k]+1;
}
printf("%I64u %I64u\n",front,rear);
return 0;
}
[C:Flying Saucer Segments,AC]
#include<stdio.h>
int m;
int make3pow(int n){
unsigned long long tmp,prod=1;
int i,j;
for(i=0;(n>>i)>0;i++){
if(((n>>i)&1)){
tmp=3;
for(j=0;j<i;j++){
tmp*=tmp;
tmp%=m;
}
prod*=tmp;
prod%=m;
}
}
return prod%m;
}
int main(void){
int n,k;
scanf("%d %d",&n,&m);
k=(int)make3pow(n);
printf("%d\n",k?(k-1):(m-1));
return 0;
}
0 件のコメント:
コメントを投稿