Code Jam 2008の問題(2)

ほしのあきらさんからコメントを頂きました。感謝です＾＾

問題が面白かったのでちょっと自分でも考えてみました。
X(i)=(3+5^0.5)^i+(3-5^0.5)^iとします。
X(i+1)=6*X(i)-4*X(i-1)
という漸化式を得られます(X(i)の両辺に((3+5^0.5)+(3-5^0.5))をかけてうまくまとめてみてください)。
これでX(0)=2、X(1)=6より、以降のX(i)を計算できます。また、下3けたに
注目するので、X(i+1)の下3けたは、X(i),X(i-1)の下3けたを使えばいいです。
これでもあってそうですかね？後でエクセルで計算してみます。

エクセルで確認してみました。
X(100)の下3けた=752
X(101)の下3けた=256
X(200)の下3けた=752
X(201)の下3けた=256
より、2つ連続で下3桁が一致するので、X(100)〜(199)の下3桁が
200〜299、300~399、400~499、…の範囲で繰り返し登場するみたいですね。

3項間漸化式で解くというのも面白いですね。

αとβはα+β=6、αβ=4だから解と係数の関係だっけ、そんなのからx^2-6x+4=0の解であることはわかります。ここから3項間漸化式に持っていって云々というやり方もあるかも知れません。逆に言うと3項間漸化式の解を求めようとすると最初の問題に戻ります。というわけで、行列のｎ乗を使ってやっぱりゴリゴリ計算することになります。

require 'matrix'

# 行列の要素へのアクセスを定義
class Matrix
	def []=(i,j,x)
		@rows[i][j]=x
	end
end

# 行列のn乗を計算
def exponentiation(matrix, n)

	if n == 1 then
		return matrix
	end
	
	if n % 2 == 0 then
		m = exponentiation(matrix, n/2)
		result = m * m
	else
		m = exponentiation(matrix, n-1)
		result = matrix * m
	end

	result[0,0] = result[0,0] % 1000
	result[1,0] = result[1,0] % 1000
	result[0,1] = result[0,1] % 1000
	result[1,1] = result[1,1] % 1000
	
	return result

end

m = Matrix[[6,-4],[1,0]]
v = Matrix[[6],[2]]

puts ((exponentiation(m,1000000000) * v)[1,0] - 1) % 1000

で、やはり解：751を得ます。

やっぱり行列のｎ乗

ｎ乗の計算は意外と速く計算することができます。計算量はO(log n)だったと思います。漸化式を1〜1000000000までコツコツ計算していくと計算量はO(n)なので数が大きいとちょっと苦しい。

ほしのさん、ありがとう。おかげさまで面白いパズルの時間になりました。

ごりごり計算してみた

a = 0
b = 6
c = 2

for i in 1..1000000000-1 do 
	a = ( 6*b - 4*c ) % 1000	
	c = b
	b = a
end

puts a - 1

というRubyスクリプトで計算したのだが、やはりというか応答がないので諦めた。で、C++で

#include 


int main()
{
	int a, b, c;
	
	b = 6;
	c = 2;
	
	for( int i = 0; i < 1000000000-1; i++ )
	{
		a = ( 6*b - 4*c ) % 1000;
		c = b;
		b = a;
	}
	
	printf("answer : %dn", a - 1 );
}

というコードを書いて実行したら、あっという間に解：-241を出力した。そ、そんな？

[onaneet@Himmel ~/Desktop]# time ./a.out
answer : -249
./a.out  8.96s user 0.09s system 95% cpu 9.515 total

なんと9秒足らずで解を出すじゃないですか（1000-241=751）。CPUはCore 2 Duoの2.33GHz。Core 2なのに1 CPUしか使わないコードであるにもかかわらずね。このコードの並列化はたぶん無理だけど。

普段、やたら重いOSとかソフトを使っているから気づかないけど、CPUって非常に速いのです。昔からそのことを知っているけど、いつになってもパソコンが快適にならないのは何故だろう。。。

おっと、いまRubyの解が出ました。

[onaneet@Himmel ~/Desktop]# time ruby go.rb
751
ruby go.rb  717.92s user 6.18s system 97% cpu 12:21.86 total

Cで書くとRubyの80倍速いのですね。まあ、この程度の差は問題のｎを100倍されたら消えちゃう程度のアドバンテージですけどね。

下手な考え休みに似たり、力ずくでやっちまってよいのかも知れません。