※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

問い142

Problem 142 「完全平方数コレクション」 †
x + y, x - y, x + z, x - z, y + z, y - zが全て平方数となる整数の組 x > y > z > 0で, 最小の x + y + z を求めよ.

解法

答えが100万近辺とか小さな数であることを祈って解いた問題。
他の人の解法を見ると私ひとり頭の悪い解法を取ってるらしい。
この問題はメモ化とかより式変形が大事だったようだ。
y=z+a1
x=z+a2とすると
x-y=a2-a1=平方数となるのでこの条件を満たすa1とa2の組み合わせを最初の2重ループで求めます。
後はこの組み合わせとzの組み合わせを全て試す2重ループで試しただけです。
zは式変形するとa1,a2の値から増加量が決まるのでzの増加数を適切にとることで計算量を抑えます。
これで約1秒で答えが出ます。



#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の表に並べ替えられる。
任意の方向(縦横斜め)に隣り合うものの和の最大値を求めよ。 (連続して足す領域は3マス以上でもよい、斜め4マス等も認める)



解法

速度とメモリを使わない方向で頑張ってみた問題。
縦横斜めで分解して一段ずつの動的計画法で正答。
そこそこ速度は出てるはず。
計算量は大雑把に言って400万*4回。


#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^3)、メモリは__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";
}