ABC125_C - GCD on Blackboard[Pythonで解いたメモ]

・[ABC125_C - GCD on Blackboard]
(https://atcoder.jp/contests/abc125/tasks/abc125_c)

N個の整数 A1,A2,....Anが入力される。
内1つを任意の整数に置き換えてみた時、N個の整数の最大公約数は幾らになるかという問題

まあよくわかんねーけど１個ずつ数字潰してgcdぶん回したら解けるやろｗをした結果・。・....

ダメな解法

何も考えずにとりあえずオレオレ実装した結果、潰す数字を変える毎に何度も端から端までgcdぶん回す事で計算量が凄いことになり頭がおかしくなって死ぬコードを書いてしまった図

    import sys
    input = sys.stdin.readline
     
    import numpy as np
    import fractions
    from functools import reduce
     
    from copy import deepcopy
     
     
    def gcd_list(nums):
        return reduce(fractions.gcd, nums)
     
    def main():
        N = int(input())
        A = np.array(sorted(list(map(int, input().split()))))
     
        bools = np.ones(N, dtype=bool)
     
        ans = 0
        vals = []
        for i in range(N):
            A_cop = deepcopy(A)
            bl_cop = deepcopy(bools)
     
            fal = [i]
            bl_cop[fal] = False
     
            vals.append(gcd_list(A_cop[bl_cop]))
     
        print(max(vals))
     
    main()

＞突然のTLE＜

よい解法

潰す数字をAiと置き、区間[A0,Ai)と区間(Ai,An]のそれぞれについて最大公約数をそれぞれ求める。
更にその2数の最大公約数を求めることでAiを潰した時に取れる最大公約数が分かるのでこの操作を全ての整数に行った後に最大の最大公約数（ゲシュタルト崩壊感）を取り出せばオッケー

キモになるのはこの方法を用いるとAiを挟み込む2つの区間の最大公約数を求める時に、1つ前のAiの最大公約数を計算した時に使った数値を持ち越して使用できるため、いちいち端から端まで何度も計算する必要がないということ

累積GCDって言うらしい
（まだ累積和にブチ当たってすらない）

    import sys
    input = sys.stdin.readline
    import fractions
    
    
    def main():
        N = int(input())
        A = list(map(int, input().split()))
    
        L_gcds = [0] * N
        L_gcd_tmp = L_gcds[0]
        for i in range(1, N):
            L_gcd_tmp = fractions.gcd(L_gcd_tmp, A[i-1])
            L_gcds[i] = L_gcd_tmp
    
        R_gcds = [0] * N
        R_gcd_tmp = R_gcds[0]
        for j in range(1, N):
            R_gcd_tmp = fractions.gcd(R_gcd_tmp, A[N-j])
            R_gcds[j] = R_gcd_tmp
        R_gcds.reverse()
    
        LR_gcds = [0] * N
        for k in range(0, N):
            LR_gcds[k] = fractions.gcd(L_gcds[k], R_gcds[k])
    
        print(max(LR_gcds))
    
    main()

学び

• 制約はちゃんと見ようね
• オレオレ実装する前に計算量をちゃんと考えよう