ABC125_C --GCD auf Blackboard [In Python gelöste Notizen]

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

N ganze Zahlen A1, A2, .... An werden eingegeben. Die Frage, wie hoch die maximale Verpflichtung von N Ganzzahlen ist, wenn eine von ihnen durch eine beliebige Ganzzahl ersetzt wird

Ich verstehe nicht wirklich, aber das Ergebnis, wenn man die Zahlen eins nach dem anderen zerquetscht und gcd herumdreht, um es zu lösen. ・ ....

Schlechte Lösung

Als Ergebnis der vorläufigen Implementierung, ohne an irgendetwas zu denken, wurde der Rechenaufwand enorm, indem gcd jedes Mal von Ende zu Ende gedreht wurde, wenn ich die zu zerquetschende Zahl änderte, und ich schrieb einen Code, der mich verrückt machte und starb

    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()

＞ Plötzlicher TLE <

Gute Lösung

Stellen Sie die zu zerquetschende Zahl als Ai ein und ermitteln Sie die maximale Verpflichtung für jedes Intervall [A0, Ai) und jedes Intervall (Ai, An]. Durch Ermitteln der maximalen Anzahl der beiden Zahlen kann außerdem die maximale Anzahl von Versprechungen ermittelt werden, die genommen werden können, wenn Ai zerquetscht wird. Es ist also in Ordnung, wenn die maximale maximale Anzahl von Versprechungen (Gestaltkollapsgefühl) nach Ausführen dieser Operation für alle ganzen Zahlen herausgenommen wird.

Wenn Sie diese Methode verwenden, können Sie den Wert, der bei der Berechnung des maximalen Versprechens des vorherigen Ai verwendet wird, übertragen, wenn Sie das maximale Versprechen der beiden Abschnitte finden, die Ai einschließen, also vom Ende an Sie müssen nicht bis zum Ende rechnen

Es scheint kumulative GCD genannt zu werden (Ich habe noch nicht einmal die kumulierte Summe erreicht)

    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()

Lernen

――Lass uns die Einschränkungen richtig sehen ――Lassen Sie uns den Rechenaufwand überlegen, bevor Sie ihn implementieren.