CodeIQ「カット・アンド・スクエア」問題に挑戦したようです

codeiq.jp

偶数 n に対して、先頭にゼロを持たない n 桁の整数で、次の条件を満たすものを考えましょう。
【条件】
 この数を上 n/2 桁と下 n/2 桁とに分け、それぞれを 2 乗して和をとると、元の数に戻る。

 ■ 第２問 （Hard）
 n = 10 の場合にこの条件を満たす全ての数の総和を求めてください。

提出したコード

rubyで。

def f(n)

	m = 10**(n/2)
	res = []
	
	ad = n > 4 ? [10, 2, 8, 10, 8, 2, 10] : [2, 6, 2]

	i = m/10
	k = 0
	
	while i < m
		i2 = i*i
		im = i*m
		s = Math.sqrt(im - i2).ceil
		e = Math.sqrt(im+m-1 - i2).floor
		
		j = s
		
		while j <= e
		
			if i2+j*j == im+j
				res << im+j
				break
			end
			j += 1
		end
		i += ad[k%ad.size]
		k += 1
	end
	res
end

puts "N=4"
puts f(4).join "\n"

puts "N=6"
puts f(6).join "\n"

puts "N=10"
puts f(10).join "\n"

puts "SUM(N=10)"
s = 0
f(10).map{|v| s += v}
puts s

方針

N桁の数の上N/2桁から下N/2桁を決定する。
たとえばN=6の時、6桁の数をAAAxxxとおくと、求めるべきxxxは√(AAA000-AAA^2)～√(AAA999-AAA^2)の間に存在する。
AAAの値を100～999まで変えて、虱潰しに計算する。
また、AAAの値の候補は(全通り調べた結果)AAAの下2桁が00,10,12,20,30,38,40,50,60,62,70,80,88,90の数字なので、それだけ調べる。

何も考えずに問題通り回ループさせると何時間かかるか考えたくもないが、こうすればだいたい回のループで済む。
実行時間は0.2秒くらい。

本当は出来る限りNの値によらず高速に答えを求めたかったけど脳ミソが足りなかったから断念した。

他に挑戦された方の回答

こちらより。togetter.com