Ruby
codeiq

まわり将棋に挑戦!

More than 1 year has passed since last update.

まず、金将の状態を列挙し、取りうる和の集合を求める。その集合の要素を8で割ったあまりに振り分ける。

T=[0,1,5,10,20]

M=8

h={}
T.repeated_permutation(4){|a|h[a.reduce(:+)]=1}
a=[0]*M
h.each_key{|k|a[k%M]+=1}

2回金将を振った時、駒が角に動く場合は、(1回めに角、2回めに角)+(1回めにあまり1、2回めにあまり7)+...+(1回めに7、2回めにあまり1)通りである。

これは以下のように乗算として定義できる。

def mul(a,b)

raise if a.size!=b.size
r=[0]*a.size
a.size.times{|i|
b.size.times{|j|
r[(i+j)%a.size]+=a[i]*b[j]
}
}
r
end

乗算として定義できれば、繰り返し二乗法を適用することができる。

e=[1]+[0]*(M-1)

n=gets.to_i
while n>0
e=mul(e,a) if n%2>0
a=mul(a,a)
n/=2
end
p e[0]

以上により、(多倍長計算を考えなければ)計算量O(logN)で求解することができた。

Ruby https://github.com/cielavenir/codeiq_solutions/blob/master/thisweek_masuipeo2/tyama_codeiq2900.rb

Python(2/3) https://github.com/cielavenir/codeiq_solutions/blob/master/thisweek_masuipeo2/tyama_codeiq2900.py