AtCoder Beginner Contest 125 - AtCoderで出題されたC - GCD on Blackboardで、累積GCDが必要になったので、組み込みのGCD
とnp.ufunc.accumulate
で実装しました。gcd
を別の関数に置き換えれば、一般に関数を累積的に適用できます。
GCD
GCD
はmath
に移行中ですが、AtCoderで利用されているPythonのバージョンではmath.gcd
が存在しません。fractions
に実装があるので次のようにして両方の差異を埋めます。
def gcd_strategy():
import math
import fractions
return math.gcd if hasattr(math, "gcd") else fractions.gcd
gcd = gcd_strategy()
累積GCD
numpy.frompyfuncを用いると、ufunc
をPythonの関数から手軽に作成できます。
gcd_ufunc = np.frompyfunc(gcd, 2, 1)
作成したufunc
を用いると、次のように累積GCDを計算できます。
numbers = [24, 18, 12, 4, 7, 2]
cumgcds = gcd_ufunc.accumulate(numbers, dtype=np.object).astype(np.int)
print(cumgcds) # [24 6 6 2 1 1]
accumulate
でdtype
の指定を行わない場合、エラーになります。
参考 : python - generalized cumulative functions in NumPy/SciPy? - Stack Overflow
おまけ
itertoolsを用いても同様のことができます。
from itertools import accumulate
import math
import fractions
gcd = math.gcd if hasattr(math, "gcd") else fractions.gcd
numbers = [24, 18, 12, 4, 7, 2]
cumgcds = accumulate(numbers, gcd)
print(list(cumgcds)) # [24 6 6 2 1 1]