問い142
Problem 142 「完全平方数コレクション」 †
x + y, x - y, x + z, x - z, y + z, y - zが全て平方数となる整数の組 x > y > z > 0で, 最小の x + y + z を求めよ.
解法
答えが１００万近辺とか小さな数であることを祈って解いた問題。
他の人の解法を見ると私ひとり頭の悪い解法を取ってるらしい。
この問題はメモ化とかより式変形が大事だったようだ。
y=z+a1
x=z+a2とすると
x-y=a2-a1=平方数となるのでこの条件を満たすa1とa2の組み合わせを最初の２重ループで求めます。
後はこの組み合わせとｚの組み合わせを全て試す２重ループで試しただけです。
ｚは式変形するとa1,a2の値から増加量が決まるのでｚの増加数を適切にとることで計算量を抑えます。
これで約１秒で答えが出ます。
#include<stdio.h>
#include<vector>
#include<set>
struct okSet{
int a1,a2,b1;
};
int main(){
std::set<int> memo;
std::vector<int> nums2;
std::vector<okSet> oks;
int t,up=1000,x,y,z;
okSet ok;
for(int i=1;i<up;i++){
memo.insert(i*i);
nums2.push_back(i*i);
for(int j=0;j<nums2.size()-1;j++){
t=nums2[i-1]-nums2[j];
if(memo.find(t)!=memo.end()){
ok.a2=nums2[i-1];
ok.a1=nums2[j];
ok.b1=2*(i+1);
oks.push_back(ok);
}
}
}
printf("%d\n",oks.size());
__int64 ans=0;
for(int i=0;i<oks.size();i++){
int add=oks[i].b1;
for(z=oks[i].b1;z<up*1000;z+=add){
x=z+oks[i].a2;
y=z+oks[i].a1;
add+=4;
if(x+y+z>ans&&ans!=0)break;
if(memo.find(x+y)==memo.end())continue;
if(memo.find(x+z)==memo.end())continue;
if(memo.find(y+z)==memo.end())continue;
if(ans==0||ans>x+y+z)ans=x+y+z;
printf("(%d %d %d)",x,y,z);
break;
}
}
printf("\nans=%d",ans);
}
問い145
解法
特定の数字の倍数のみしかこの条件を満たさないみたいですが、探索範囲が十億までの数と狭いので全部試してみました。
#include<stdio.h>
bool okKisuu(int a){
while(a!=0){
if((a%10)%2==0)return false;
a/=10;
}
return true;
}
int rev(int a){
int re=0;
while(a!=0){
re=re*10+a%10;
a/=10;
}
return re;
}
int main(){
int ans=0;
for(int a=1;a<10000*10000*10;a++){
if(a%10==0)continue;
ans+=okKisuu(rev(a)+a);
}
printf("%d",ans);
}
問い149
下の表において、任意の方向(縦横斜め)に隣り合うものの和の最大値は16 (= 8 + 7 + 1)となることは簡単に確かめられる。
-2 5 3 2
9 -6 5 1
3 2 7 3
-1 8 -4 8
いま、同じ探索をより大きなものについてもしてみることにする。
まず、400万個の擬似乱数を"Lagged Fibonacci Generator"によって生成する。
1 ≤ k ≤ 55 について、sk = [100003 - 200003k + 300007k3] (modulo 1000000) - 500000
56 ≤ k ≤ 4000000 について、sk = [sk-24 + sk-55 + 1000000] (modulo 1000000) - 500000
つまり、s10 = -393027 , s100 = 86613 となる。
s の項は、最初の2000個を最初の行に(順番に)、次の2000個を2番目の行に、というように、2000x2000の表に並べ替えられる。
任意の方向(縦横斜め)に隣り合うものの和の最大値を求めよ。 (連続して足す領域は３マス以上でもよい、斜め４マス等も認める)
解法
速度とメモリを使わない方向で頑張ってみた問題。
縦横斜めで分解して一段ずつの動的計画法で正答。
そこそこ速度は出てるはず。
計算量は大雑把に言って４００万*４回。
#include<stdio.h>
#include<string.h>
#include<algorithm>
int main(){
int lines[4001],memoLR[2002],memoUD[2002],memoRU[2002],memoLU[2002],nextRU[2002];
__int64 temp;
__int64 mod=1000000,del=500000;
int ans=-mod*10;
for(int k=1;k<=55;k++){
lines[k]=(((__int64)(k*k*k))*300007-200003*k+100003)%mod-del;
memoLR[k]=memoUD[k]=memoRU[k]=memoLU[k]=lines[k];
}
for(int k=56;k<=2000;k++){
lines[k]=(lines[k-24]+lines[k-55]+mod)%mod-del;
memoLR[k]=memoUD[k]=memoRU[k]=memoLU[k]=lines[k];
}
for(int r=2;r<=2000;r++){
for(int k=2001;k<=4000;k++){
lines[k]=(lines[k-24]+lines[k-55]+mod)%mod-del;
int p=k-2000;
int val=lines[k];
if(p==1){
memoLU[1]=memoRU[1]=memoLR[1]=val;
}else if(p==2000){
memoLR[p]=std::max(memoLR[p-1]+val,val);
memoLU[p]=std::max(memoLU[p-1]+val,val);
memoRU[p]=val;
}else{
memoLR[p]=std::max(memoLR[p-1]+val,val);
memoLU[p]=std::max(memoLU[p-1]+val,val);
nextRU[p]=std::max(memoRU[p+1]+val,val);
}
memoUD[p]=std::max(memoUD[p]+lines[k],lines[k]);
ans=std::max(memoUD[p],ans);
ans=std::max(memoLU[p],ans);
ans=std::max(nextRU[p],ans);
ans=std::max(memoLR[p],ans);
}
memcpy(&memoRU[1],&nextRU[1],sizeof(int)*2000);
memmove(&lines[1],&lines[2001],sizeof(int)*2000);
}
printf("%d",ans);
}
問い150
理論値 計算量O(1000＾３)、メモリは__int64で100万個と少しばかりの配列を消費。
少しばかりめんどくさかったがまあ動的計画法としては単純。
#include<stdio.h>
#include<iostream>
#include<string.h>
__int64 memo[1002][1002],sum[1001]={0};
int main(){
__int64 ans=273519,s,t=0,m20=(1<<20),m19=(1<<19),d;
memset(memo,0,sizeof(memo));
for(int r=1;r<=1000;r++){
memset(sum,0,sizeof(sum));
for(int c=1;c<=r;c++){
t=(615949*t+797807)%m20;
sum[c]=sum[c-1]+t-m19;
}
for(int c=r;c>0;c--){
for(int c2=0;c2<c;c2++){
d=sum[c]-sum[c2];
memo[c][c-c2]=d+memo[c-1][c-c2-1];
if(ans>memo[c][c-c2])ans=memo[c][c-c2];
}
}
}
std::cout<<ans<<"\n";
}
最終更新：2012年11月27日 17:19
