問い1
#include<stdio.h>
int main(){
printf("%d",333*167*3+199*100*5-33*67*15);
}
問い2
解法
フィボナッチ数列は最初奇数、奇数で始まり
奇数+奇数=偶数
奇数+偶数=奇数
偶数+奇数=奇数
奇数+奇数=偶数
で偶数が3つごとに現れます。
そしてn=3k番目のフィボナッチ数列の項を求める関数をf(n)としたとき数式を展開することで
f(n)=4*f(n-3)+f(n-6)が常に成り立ちつことが容易に判明します。
後はこれをそのままプログラムにするだけです。
もしかしたらもうひとつ深く考えて行列演算を使えば、ループを行うまでもなく一発で答えが出るかもしれません。
#include<stdio.h>
int main(){
int ans=0,y=0,z=2,t;
while(z<=400*10000){
t=z*4+y;
y=z;
z=t;
ans+=y;
}
printf("%d",ans);
}
問い3
3195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
解法
とりあえず試し割をしてみましたが数の特殊性に注目したもう少し賢い方法があるかもしれません。
#include<iostream>
int main(){
__int64 num=600851475143L;
for(__int64 i=2;i*i<=num;i+=(i&1)+1){
while(num%i==0){
std::cout<<i<<" ";
num/=i;
}
}
if(num!=1)std::cout<<num;
}
問い4
力づくの方法以外をコードをに組み込むとコードが長くなるのでとりやめました。
もし7桁の数同士の掛け算とかとなると難しい。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
bool isOK(char* str){
int len=strlen(str);
for(int i=0;i<len/2;i++){
if(str[i]!=str[len-i-1])return false;
}
return true;
}
int main(){
char str[7];
int ans=0;
for(int i=100;i<1000;i++){
for(int j=100;j<1000;j++){
int m=i*j;
sprintf(str,"%d",m);
if(isOK(str)&&ans<m)ans=m;
}
}
printf("%d",ans);
}
問い5
#include<stdio.h>
#include<map>
#include<math.h>
#include<iostream>
void calc(int n){
int num;
std::map<int,int> anss;
for(int i=2;i<=n;i++){
num=i;
for(int j=2;j*j<=n;j++){
int count=0;
while(num%j==0){
num/=j;
count++;
}
if(count>0){
if(anss.find(j)==anss.end()||anss[j]<count)anss[j]=count;
}
}
if(num!=1){
if(anss.find(num)==anss.end()||anss[num]<1)anss[num]=1;
}
}
int ans=1;
for(std::map<int,int>::iterator it=anss.begin();it!=anss.end();it++){
std::cout<<(*it).first<<" "<<(*it).second<<"\n";
ans*=pow((*it).first,(*it).second);
}
std::cout<<ans;
}
int main(){
calc(20);
}
問い6
解法
プログラムを書くまでもなく数式で一発です。
#include<stdio.h>
#include<math.h>
int calc(int n){
return (3*pow(n,4)+2*pow(n,3)-3*pow(n,2)-2*n)/12;
}
int main(){
printf("%d",calc(100));
}
問い7
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10 001 番目の素数を求めよ.
解法
素数が絡むと問題の難易度が低く設定されやすくなるように思えます。
素数の判定や素数にかかわる性質は複雑で高度なために一般の参加者が知らない性質が増えます。
そのため専門知識がなくても解けるよう試し割程度で片がつく問題が出題されやすくなります。
高度な専門知識がなくても柔軟な発想力で参加できる、これが競技プログラムの良さだと思います。
#include<stdio.h>
#include<math.h>
bool isPrime(int n){
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
int main(){
int count=1,ans=3;
while(1){
if(isPrime(ans)==true)count++;
if(count>=10001)break;
ans+=2;
}
printf("%d",ans);
}
問い8
1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか.
解法
尺取り虫法で高速化する方法も考えてみましたが5文字程度では大差がつかないのでやめました。
#include<stdio.h>
int main(){
char text[1002]="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
int ans=0;
for(int i=0;i<1000;i++)text[i]-='0';
for(int i=0;i<996;i++){
int k=text[i]*text[i+1]*text[i+2]*text[i+3]*text[i+4];
if(ans<k)ans=k;
}
printf("%d",ans);
}
問い9
ピタゴラスの三つ組(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.
a2 + b2 = c2
例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である.
a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.
解法
原始ピタゴラス数の公式からかなり絞り込めます。
#include<stdio.h>
int main(){
for(int m=2;m*(m+1)<=500;m++){
for(int n=1;m*(m+n)<=500&&n<m;n++){
int k=m*(m+n);
if(500%k==0){
int t=500/k;
printf("ans=%d %d %d ans=%d",t*(m*m-n*n),t*2*m*n,t*(m*m+n*n),t*t*t*(m*m-n*n)*(2*m*n)*(m*m+n*n));
}
}
}
}
問い10
200万以下の素数の和を求めよ。
解法
素数かどうか試し割で調べて足しこむだけです。
#include<stdio.h>
#include<iostream>
bool isPrime(int n){
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
int main(){
__int64 ans=2;
for(int i=3;i<=200*10000;i+=2)if(isPrime(i))ans+=i;
std::cout<<ans;
}
最終更新:2012年12月12日 22:57