Algorithmes de base utilisables par les pros de la compétition

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

Problème de débit maximum (Ford Falkerson)

Ici l'article est facile à comprendre Je vais l'implémenter bientôt ...

Recommended Posts

Algorithmes de base utilisables par les pros de la compétition
Peut être utilisé chez les pros de la compétition! Bibliothèque standard Python
Résumé de l'entrée standard de Python pouvant être utilisée dans Competition Pro
Fonctions pouvant être utilisées dans l'instruction for
Enregistrement d'image ANT qui peut être utilisé en 5 minutes
Goroutine (contrôle parallèle) utilisable sur le terrain
Goroutine utilisable sur le terrain (édition errgroup.Group)
Scripts pouvant être utilisés lors de l'utilisation de Bottle en Python
Un minuteur (ticker) qui peut être utilisé sur le terrain (peut être utilisé n'importe où)
Remplissage facile des données pouvant être utilisées dans le traitement du langage naturel
Python-Sound device Module de traitement du signal acoustique ASIO [Basic]
Types de fichiers pouvant être utilisés avec Go
Construire un Sphinx qui peut être écrit avec Markdown
Utilisation des fonctions récursives utilisées chez les pros de la compétition
Notes personnelles des opérations liées aux pandas qui peuvent être utilisées dans la pratique
Programme d'installation facile et programme de mise à jour automatique pouvant être utilisé dans n'importe quelle langue
Commande Linux (édition de base) utilisable à partir d'aujourd'hui si vous connaissez
Pour pouvoir utiliser le japonais avec Python dans l'environnement Docker
Notes sur les connaissances Python utilisables avec AtCoder
[Django] À propos des utilisateurs pouvant être utilisés sur un modèle
Résumé des méthodes d'analyse de données statistiques utilisant Python qui peuvent être utilisées en entreprise
Connaissance de base du DNS qui ne peut pas être entendue maintenant
Analyse de texte pouvant être effectuée en 5 minutes [Word Cloud]
Index d'évaluation pouvant être spécifié pour GridSearchCV de sklearn
Liste de mes articles pouvant être utiles aux pros de la compétition (mise à jour de temps en temps)
[Django] Noms de champs pouvant être utilisés pour le modèle utilisateur, l'enregistrement des utilisateurs et les méthodes de connexion
[Python3] Code qui peut être utilisé lorsque vous souhaitez redimensionner des images dossier par dossier
Je l'ai fait parce que je veux des données JSON qui peuvent être utilisées librement dans les démos et les prototypes
[Python] Connaissances de base utilisées dans AtCoder
Créez une Spinbox qui peut être affichée en binaire avec Tkinter
33 chaînes à ne pas utiliser comme noms de variables en python
Gestion des chaînes de caractères dans la communication JSON
Nouvelles fonctionnalités de Python 3.9 (1) -L'opérateur d'ensemble de somme peut être utilisé dans le type de dictionnaire.
Confirmation que rkhunter peut être installé
Créez une Spinbox pouvant être affichée dans HEX avec Tkinter
Module standard Python utilisable en ligne de commande
J'ai écrit un tri-arbre qui peut être utilisé pour l'implémentation de dictionnaire à grande vitesse en langage D et Python
À propos du fait que l'objet recompilé peut être utilisé pour le modèle re.match
Module de traitement du signal acoustique qui peut être utilisé avec Python-Sounddevice ASIO [Application]
Masquer l'avertissement selon lequel zsh peut être utilisé par défaut sur Mac
Bot LINE sans serveur qui peut être réalisé en 2 heures (acquisition de l'identifiant source)
Optimisation mathématique pour un travail gratuit avec Python + PuLP
Nombre maximum de paramètres de fonction pouvant être définis dans chaque langue
Une histoire que heroku, qui peut se faire en 5 minutes, a en fait duré 3 jours
[Python3] Code qui peut être utilisé lorsque vous souhaitez découper une image dans une taille spécifique
Contrôle QPS utilisable sur le terrain (Rate Limit) Limite l'exécution à n fois par seconde
[2015.02.22] Youtube-dl a été mis à jour et ne peut plus être utilisé dans les versions précédentes.
Je souhaite créer une file d'attente prioritaire pouvant être mise à jour avec Python (2.7)
Si "ne peut pas être utilisé lors de la création d'un objet PIE" apparaît dans make
Résumé des sources de données scikit-learn pouvant être utilisées lors de la rédaction d'articles d'analyse
Comment installer la bibliothèque Python qui peut être utilisée par les sociétés pharmaceutiques
Cela peut être réalisé en 1 minute! Le décorateur qui met en cache l'exécution de la fonction entraîne Memcached
Module de grattage "Gaspacho" qui peut être utilisé plus facilement que Beautiful Soup
Liste des outils qui peuvent être utilisés pour essayer facilement l'analyse des émotions des phrases japonaises avec Python (essayez avec google colab)
++ et-ne peuvent pas être utilisés pour incrémenter / décrémenter en python
Jusqu'à ce que vous puissiez utiliser youtube-dl avec Synology (DS120j)
Répertorier les packages pouvant être mis à jour avec pip
Le problème que la commande ifconfig ne peut pas être utilisée
Présentation et fonctionnalités utiles de scikit-learn qui peuvent également être utilisées pour l'apprentissage en profondeur
Convertir des images du SDK FlyCapture en un formulaire pouvant être utilisé avec openCV