ABC125_C --GCD sur tableau noir [Notes résolues en Python]

・ [ABC125_C --GCD sur tableau noir] (https://atcoder.jp/contests/abc125/tasks/abc125_c)

N entiers A1, A2, .... An sont saisis. La question de savoir quel est l'engagement maximum de N entiers lorsque l'un d'entre eux est remplacé par un entier arbitraire

Je ne comprends pas vraiment, mais le résultat d'écraser les nombres un par un et de tourner le pgcd pour le résoudre. ・ ....

Mauvaise solution

Du fait de l'implémenter pour le moment sans penser à rien, la quantité de calcul est devenue énorme en tournant pgcd de bout en bout à chaque fois que j'ai changé le numéro pour être écrasé, et j'ai écrit un code qui m'a rendu fou et est mort

    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 soudain <

Bonne solution

Définissez le nombre à écraser comme Ai, et trouvez l'engagement maximum pour chacun des intervalles [A0, Ai) et de l'intervalle (Ai, An]. De plus, en trouvant les promesses maximales de ces deux nombres, les promesses maximales qui peuvent être prises lorsque Ai est écrasé peuvent être trouvées, il est donc normal que les promesses maximales maximales (sentiment d'effondrement de la Gestalt) soient retirées après avoir effectué cette opération sur tous les nombres entiers.

Si vous utilisez cette méthode, vous pouvez reporter la valeur utilisée lors du calcul de la promesse maximale de l'Ai précédent lors de la recherche de la promesse maximale des deux sections qui sandwich Ai, donc à partir de la fin Vous n'êtes pas obligé de calculer jusqu'au bout

Cela semble s'appeler GCD cumulatif (Je n'ai même pas encore atteint la somme cumulée)

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

Apprendre

―― Voyons bien les restrictions ―― Pensons à la quantité de calcul avant de l'implémenter.