問い171
正の整数nについて、f(n)を各桁の数字(10進数)の平方の和と定義する。例えば、
f(3) = 3^2 = 9,
f(25) = 2^2 + 5^2 = 4 + 25 = 29,
f(442) = 4^2 + 4^2 + 2^2 = 16 + 16 + 4 = 36
0 < n < 10^20について、f(n)が平方数となるようなnの和の末尾9桁を求めよ。
f(ｎ)が平方数となる数の個数なら簡単にもとまるんだけどな、、
ひと工夫必要だな。
と思ったら色々試行錯誤した結果１時間ほどで正答。
意外と簡単なコードになった。
１時間、かかり過ぎなのでもっと精進せねばなるまい。
memoは組み合わせ数の動的計画法、sumsは和の合計値の動的計画法。
memo[各桁の２乗の和]＝となるのが何通りか、sums[各桁の２乗の和]＝合計がいくつか,。
この問題正答者だけが見れる掲示板で見たらPythonで何か恐ろしいコードをあげている人がいた。
29とか41とか意味不明なマジックナンバーを使って問題を解いている。
ああいうのをハッカーというのだろう。
あれから見たら私のコードなんか子供じみた発想のお坊ちゃんコードだな。
その代わり私のコードは教科書通りで丁寧なつもり。
#include<stdio.h>
#include<string.h>
#include<iostream>
const int up=2000;
int main(){
__int64 memo[up+2],sums[up+2],base=1000000000,mul=0,t2;
int t;
memset(memo,0,sizeof(memo));
memset(sums,0,sizeof(sums));
memo[0]=1;//20桁について動的計画法で解く
for(int i=0;i<20;i++){
if(i==11)mul=base;//sumsによる動的計画法の解禁
mul/=10;
//std::cout<<i<<" "<<mul<<"\n";
for(int num=up;num>=0;num--){
for(int k=9;k>=1;k--){
t=k*k;
if(t+num>up)continue;
t2=((mul*(k*memo[num])%base)%base+sums[num])%base;
memo[t+num]=(memo[t+num]+memo[num])%base;
sums[t+num]=(sums[t+num]+t2)%base;
}
}
}
__int64 ans=0;
for(int i=1;i*i<=up;i++){
ans=(ans+sums[i*i])%base;
}
std::cout<<ans<<"\n";
}
問い172
saiki関数で18桁で使う各数字の個数を決めたら、deep==ketaでその数字の配置個数を計算するだけです。
内容的には高校数学の延長ですね。
#include<stdio.h>
#include<string.h>
#include<iostream>
const int keta=18;
int count[10]={0};
__int64 ans=0;
__int64 nCr(int n,int r){
__int64 re=1;
for(int i=0;i<r;i++){
re*=(n-i);
}
for(int i=1;i<=r;i++){
re/=i;
}
return re;
}
void saiki(int deep,int p){
if(deep==keta){
//0を先頭以外の１７か所に配置する
__int64 a=nCr(17,count[0]);
int b=18-count[0];
//残りの数字の配置を計算する
for(int i=1;i<10;i++){
a*=nCr(b,count[i]);
b-=count[i];
}
ans+=a;
}else{
for(int i=p;i<10;i++){
if(count[i]<3){
count[i]++;
saiki(deep+1,i);
count[i]--;
}
}
}
}
int main(){
saiki(0,0);
std::cout<<ans;
}
問い173
解法
サイズｎの正方形の真中に穴をあけた場合の計算式n^2-(n-2)^2<=100万を満たす範囲がｎの最大値となるのでこれを計算して後は2乗した数をmapに入れておくだけです。
メモリをぜいたくに使ったこの一品。
贅沢に使いすぎてるかもしれませんがそのかわりコードがシンプルになってます。
n=３から真中の穴の範囲を広げていけばメモリ使用量を抑えられる気もしますが少しコードが複雑になります。
#include<stdio.h>
#include<map>
#include<iostream>
#include<time.h>
int main(){
__int64 tile=1000*1000;
__int64 limit=tile/4+1;
__int64 S,ans=0,herf;
std::map<__int64,int> sqrtTable;
for(__int64 i=0;i<=limit-2;i++){
sqrtTable[i*i]=i;
}
for(__int64 i=3;i<=limit;i++){
S=i*i-tile;
int k=(*sqrtTable.lower_bound(S)).second;
k=k==0?(i-1)/2:(i-k)/2;
ans+=k;
}
std::cout<<ans;
}
問い178
45656を考えよう. 連続する2桁の数は全て差の絶対値が 1 である.
連続する2桁の数の差の絶対値が全て 1 である数をステップ数と呼ぶ.
Pandigital数では0から9の各数が少なくとも 1 回出現する.
10^40未満の数でPandigital数かつステップ数であるものの数を答えよ.
この問題も動的計画法でいいと思うけど３次元なのですこし処理がめんどくさい。
２次元だと紙にかいて確認できるから楽でいいなと思う次第。
まあ３次元といっても動的計画法の実質各ターンは２次元みたいなものか。
#include<stdio.h>
#include<iostream>
#include<string.h>
//memo[i桁目][出た数字の数][先頭桁の数字]少し多めに確保してるのは私の癖です
__int64 memo[42][1026][11];
int main(){
memset(memo,0,sizeof(memo));
for(int i=0;i<10;i++)memo[1][(1<<i)][i]=1;//一ケタ目の設定
__int64 ans=0;
for(int k=1;k<40;k++){
//桁数
for(int p=0;p<1024;p++){
//出た数字の組み合わせ
for(int i=0;i<10;i++){
//手前の数
if(0<i){
memo[k+1][p|(1<<(i-1))][i-1]+=memo[k][p][i];
}
if(i<9){
memo[k+1][p|(1<<(i+1))][i+1]+=memo[k][p][i];
}
}
}
for(int i=1;i<10;i++){
ans+=memo[k+1][1023][i];
}
}
std::cout<<ans;
}
問い179
n と n + 1 の正の約数の数が同じになる 1 < n < 107 の整数は幾つあるか。 例として, 14 の正の約数は 1, 2, 7, 14 であり, 15 の正の約数は 1, 3, 5, 15 である.
うーん愚直に求めてみたけどもっと賢い方法がありそう、、、
#include<stdio.h>
#include<math.h>
int calc(int n){
int k=sqrt(n);
int p=1;
while(n%2==0){
n/=2;
p++;
}
for(int i=3;i<=k;i+=2){
int r=1;
while(n%i==0){
n/=i;
r++;
}
p*=r;
}
if(n!=1)p*=2;
return p;
}
int main(){
int old=0,now,ans=0;
for(int i=2;i<10000001;i++){
now=calc(i);
if(old==now){
printf("%d %d\n",i,now);
ans++;
}
old=now;
}
printf("%d",ans);
}
最終更新：2012年11月25日 18:07
