ABC285-C
問題概要
A,B,C,...,X,Y,Z,AA,AB,AC,...ZX,ZY,ZZ,AAA,AAB...という文字列の列と1,2,3,...,24,25,26,27,28,29...,700,701,702,703,704,...という数字を対応させるとき、与えられた文字列と対応する数字を出力せよ。
解答
例えば、与えられた文字列がCBAなら、その前には、長さ1の文字列が26^1個、長さ2の文字列が26^2個、あって、その次に、長さ3の文字列が、AAAからBZZまで2*26^2個、CAAからCAZまで1*26^1個、その次の文字がCBAなので、26^1+26^2+2*26^2+1*26^1+1が対応いる数字となる。
一般化すると、与えられた文字列がn文字からなっていれば、まずその前に、長さ1の文字列が26^1個、...、長さn-1の文字列が26^(n-1)個あるので、初期値0にこれを加算していく。次に、長さnの文字列が与えられた文字列の前に何個あるか考える。i番目(0オリジン)の文字のアスキーコードから65を引いた値をm[i]とすると、m[0]*26^(n-1)+m[1]*26^(n-2)+...+m[n-2]*26^1+m[n-1]個である。この部分、具体的には、先頭桁から、これまでの和に26を乗じ、その桁の文字のアスキーコード-65を加えることを繰り返して行った。最後に1を加えると、与えられた文字列の番号になる。
以下が、本番で提出したコード。
s=gets.chomp
ans=0
n=s.size
(1...n).each do |i|
t=26.pow(i)
ans+=t
end
tt=0
n.times do |i|
tt*=26
t=s[i].ord-65
tt+=t
end
ans+=tt
puts ans+1
中学受験算数で群数列をやりなれていると、こういう問題は割合と簡単に思える。(実際、今回はC問題の方がB問題よりも簡単だった。)
上が本番で提出したコード。Cで書いたのが以下。
long long ll_pow(long long x, long long n);
#include<stdio.h>
#include<stdlib.h>
#define N 14
int main(void){
char* s=(char*)malloc(sizeof(char)*N);
fgets(s,N,stdin);
long long ans=0,t=0;
int length=0;
while(s[length]>=65 && s[length]<=90)length++;
// printf("length=%d\n",length);
ans+=((26*(1-ll_pow(26,length-1))/(1-26)));
// printf("sum1=%d\n",ans);
for(int i=0;i<length;i++){
t*=26;
t+=(s[i]-65);
}
t++;
ans+=t;
printf("%lld\n",ans);
free(s);
/* for(int i=1;i<12;i++){
printf("%lld\n",ll_pow(26,i));
}*/
return 0;
}
long long ll_pow(long long x, long long n){
long long ret=1;
while(n>0){
if((n&1)==1)ret*=x;
x*=x;
n>>=1;
}
return ret;
}
やりかたは基本的にrubyでやった時と同じで、与えられた文字列がn文字からなる場合、n-1個までの文字からなる文字列の個数の個数の和( 26+26^2+26^3+...+26^(n-1) )を求める部分と、与えられたn個の文字からなる文字列を26進法で表された数値とすると、それが10進法で何になるか(厳密に言うと、ここで最初の数は0なので、「何番目か」という問いに答えるには1を足す必要がある)を求める部分とからなる。この前半部分について、今回は少し趣向を変えて、等比数列の和を求める公式を使って求めた。
あと、今回必要になったのは、最初の文字列の読み込みをする際に何文字分のメモリを確保すればいいかを知るために、26+26^2+26^3+...+26^(n-1) < 10^16 を満たす最大のnを求めること。制約が、文字列の文字数ではなく、1個からn個までからなる文字列の累計の個数として与えられているためだ。上の不等式の左辺は26*(1-26^(n-1))/(1-26)=26*(26^(n-1)-1)/25。よって、26*(26^(n-1)-1)/25 < 10^16 とし、両辺の10を底とする対数を取ると、log10(26)+log10(26^(n-1)-1)-log10(25) < 16。ここで、(26^(n-1)-1)は26^(n-1)にほぼ等しいとみなして計算すると、log10(26)+(n-1)*log10(26)-2*log10(5) < 16。
log10(26)=1.415 (なお、これは、常用対数表でlog10(2.6)=0.415 となっているのを読んで、log10(26)=log10(2.6*10)=log10(2.6)+log10(10)=1.415) として求められる。log10(5)=0.699 を代入して、n*1.415-2*0.699 < 16。n < 12.1。となって、nの文字数は最大で12と分かる。(後になって気づいたが、これは自分で計算しなくても、入出力例の最後に書いてあった。)
2進数
ABC306-B
問題概要
a[0],a[1],...a[n-2],a[n-1]が、それぞれx^0,x^1,...,x^(n-2),x^(n-1)の係数である。x=2として、この数を10進法で出力せよ。(n=64, a[0],a[1],...a[n-2],a[n-1]は0または1)
解答
a=gets.chomp.split(" ").map(&:to_i)
s=a.reverse.join("")
puts s.to_i(2)
与えられた配列は順に2進法での大きい桁の方からの数になるので、文字列を逆順にしてから2進法→10進法の変換を行うと、求める値が得られる。
上が本番で提出したコードだが、xが2以外の一般の数でも使えるようにしたのが、次のコード。
a=gets.chomp.split(" ").map(&:to_i)
n=0
t=1
base=2
a.size.times do |i|
n+=a[i]*t
t*=base
end
puts n
Cでやった一つ目のコードが以下。
void print_ivector(int* a,int n);
#include<stdio.h>
#include<stdlib.h>
#define N 130
#define N2 64
int main(void){
char *s=(char*)malloc(sizeof(char)*N);
int* a=(int*)malloc(sizeof(int)*N2);
fgets(s,N,stdin);
int i=0,j=0;
while(*(s+i)!=0 && *(s+i)!='\n'){
if(*(s+i)==48 || *(s+i)==49){
*(a+j)=*(s+i)-48;i++;j++;
}else if (*(s+i)==32)i++;
}
// print_ivector(a,N2);
unsigned long long num=0,t=1;
for(int i=0;i<N2;i++){
num+=a[i]*t;
t*=2;
}
printf("%llu\n",num);
return 0;
}
void print_ivector(int* a,int n){
for(int i=0;i<n-1;i++){
printf("%d ",*(a+i));
}
printf("%d\n",*(a+n-1));
}
a[0],a[1],...a[n-2],a[n-1]が全て1だった場合、この数は 2^64-1 になる。符号なし64ビット整数の最大値だ。十進法では、log10(2^64)=64*log10(2)=64*0.301=19.262 だから、およそ 10^19.262=(10^0.262)*10^19=1.836*10^19となる。ちなみに、2^64-1の十進法での正確な値は 18,446,744,073,709,551,615 である。というわけで、ここは unsigned long long を使うしかない。
もう一つが以下。
#include<stdio.h>
#include<stdlib.h>
#define N 130
#define N2 64
int main(void){
char *s=(char*)malloc(sizeof(char)*N);
int* a=(int*)malloc(sizeof(int)*N2);
fgets(s,N,stdin);
int i=0,j=0;
while(*(s+i)!=0 && *(s+i)!='\n'){
if(*(s+i)==48 || *(s+i)==49){
*(a+j)=*(s+i)-48;i++;j++;
}else if (*(s+i)==32)i++;
}
unsigned long long num=0;
for(int i=N2-1;i>=0;i--){
num*=2;
num+=a[i];
}
printf("%llu\n",num);
return 0;
}
こちらの方が僅かだが時間は余計にかかるようだ。
0 件のコメント:
コメントを投稿