Quel article?

J'ai essayé de lister les algorithmes utilisables chez les pros de la compétition.

* Mis à jour de temps en temps

Jugement des nombres premiers (tamisage des élatostines)

https://atcoder.jp/contests/abc084/tasks/abc084_d


from itertools import accumulate
import math
m = 10**5

L = [x for x in range(2,m+1)]

#Extraire les nombres premiers avec un tamis d'ératostènes
for y in range(2, int(math.sqrt(m)+1)):
    L = [z for z in L if(z == y or z % y != 0)]

#N+1/Extrayez ce que 2 est aussi un nombre premier
P = []
for w in L:
    if (w+1)/2 in L:
        P.append(w)

#Créé pour la somme cumulée
G = [0] * (m+1)
for i in P:
    G[i+1] = 1

#Somme cumulée
Q = list(accumulate(G))



n = int(input())
for _ in range(n):
    s, t = map(int, input().split())
    print(Q[t+1]-Q[s])




'''
Les nombres premiers suivants sont lents.
Utilisez le tamis Eratostenes comme ci-dessus

def isPrime(n):

    if n == 1:
        return False
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)+1), 2):
        if n % i == 0:
            return False
    return True

'''

Bit méthode de planification dynamique (problème de vendeur de patrouille)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A

v, e = map(int, input().split())

inf = 10**7
edges = [[inf]*v for _ in range(v)]

for i in range(e):
    s, t, d = map(int, input().split())
    edges[s][t] = d

#Dp est le coût minimum dans S lorsque l'ordre est optimisé sous la contrainte que v est le dernier pour le sous-ensemble S de l'ensemble.
dp = [[inf]*v for _ in range(2**v)]
dp[0][0] = 0

#Set (nombre binaire indiquant s'il est visité ou non)
for x in range(2**v):
    #Dernier nœud visité
    for y in range(v):
        #Nœuds autres que le dernier visité
        for z in range(v):
            #1.Si vous avez déjà visité 2.N'est-ce pas le dernier nœud visité 3.Y et z sont-ils connectés en premier lieu?
            if ((x >> y) & 1) and y != z and edges[z][y] < 10**6:
                dp[x][y] = min(dp[x][y], dp[x^(1<<y)][z]+edges[z][y])

if dp[-1][0] > 10**6:
    print(-1)
else:
    print(dp[-1][0])

Problème d'itinéraire le plus court (méthode de Bellmanford)

J'ai fait référence à ici. De plus, l'explication sur Bellman Ford était facile à comprendre dans l'article ici.


#v:Pic e:Côté
v, e = map(int, input().split())
#Liste pour stocker les arêtes (ni matrice adjacente ni liste adjacente)
edges = []

for _ in range(e):
    s, t, w = map(int, input().split())
    edges.append([s, t, w])
    # edges.append([t, s, w])

#Moins que,Bellmanford
def bellman_ford(start,goal,edges,v):
    #Initialisation à distance
    distance = [float("inf")] * v
    distance[start] = 0
    
    for i in range(v):
        #Si la distance a été mise à jour
        updated = False
        for s, t, w in edges:
            if distance[t] > distance[s] + w:
                distance[t] = distance[s] + w
                updated = True
        #Preuve que l'itinéraire le plus court est trouvé lorsque la distance n'est plus mise à jour
        if not updated:
            break
        #Même s'il est mis à jour v fois, la mise à jour de l'itinéraire le plus court ne se termine pas → Il y a un itinéraire fermé négatif
        if i == v - 1:
            return -1
    return distance[goal]

for i in range(v):
    print(bellman_ford(0, i, edges, v))