Une collection de techniques professionnelles compétitives à résoudre avec Python

Quel genre d'article

Merci. Je vais résumer le style d'écriture propre au pro de la concurrence dont j'avais besoin (@ rainline00) pour résoudre les questions passées du concours Atcoder Begginers avec python. Je l'ajouterai de temps en temps.

index

Comment écrire

[Entrée](# entrée) [Recherche d'élément de liste](# Recherche d'élément de liste)

Liés à l'algorithme

[Rechercher tout](# Rechercher tout) [Engagement maximum / multiple commun minimum](# engagement maximum minimum commun multiple) [Somme cumulée](# Somme cumulée) [Combination / Order](# Combination Order) [Recherche de priorité de profondeur / recherche de priorité de largeur](# recherche de priorité de profondeur recherche de priorité de largeur)

contribution

Il est facile d'oublier les entiers qui sont entrés un par un sur n lignes.

python

s = input() #Chaîne
n = int(input()) #Valeur entière
a, b = map(int, input().split()) #Deux entiers ou plus
li = list(map(int, input().split())) #list
li2 = [int(input()) for _ in range(n)] #Un entier saisi un par un sur n lignes

Recherche d'élément de liste

list.index (n) renvoie un seul index avec des valeurs correspondantes. Renvoie plusieurs valeurs dans une liste en utilisant la notation d'inclusion de liste.

python

li = [0, 2, 1, 4, 2, 3, 2] 
indexes = [i for i, x in enumerate(li) if x == 2] #Rechercher 2
print(indexes) # [1, 4, 6]

Recherche complète

recherche peu complète

Si vous pouvez énumérer tous les cas tels que "utiliser ou ne pas utiliser" pour chaque variable ($ O (2 ^ N) $ suffit), vous pouvez utiliser la recherche complète de bits. Le nombre total de chiffres représentant «utiliser ou ne pas utiliser» est pris par le nombre de variables. Il ne peut être représenté que par un seul nombre binaire.

Exemple: ABC167C --Skill Up

Répertoriez tous les états $ 2 ^ n $ de «acheter ou ne pas acheter» pour chaque livre de référence et déterminer si les conditions sont remplies. En utilisant ʻarray de numpy`, il peut être décrit rapidement et de manière concise.

abc167.py

import numpy as np

n, m, x = map(int, input().split())
li = [np.array(map(int, input().split())) for _ in range(n)]
ans = 10 ** 10
comp = np.array([x for _ in range(m)])

for i in range(1 << n):
    sum = np.array([0 for _ in range(m + 1)])
    now = i
    for j in range(n):
        di = now % 2
        now = now >> 1
        if di == 1:
            sum += li[j]
    
    if all(sum[1:m+1] >= comp):
        ans = min(ans, sum[0])

if ans == 10 ** 10:
    print(-1)
else:
    print(ans)

Engagement maximum / multiple commun minimum

Lors de la recherche des multiples communs maximum et minimum de plusieurs variables, il peut être écrit de manière récursive en utilisant la fonction d'ordre supérieur réduire (). Le python d'atcoder est la version 3.4.3 (au 31 décembre 2019), utilisez donc le module fractions au lieu du module math. </ del> (Ajouté le 19 mai 2020) Le Python d'Atcoder a été mis à jour vers la version 3.8.2! Utilisons le module math

python

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm, numbers)

Somme cumulée

Un algorithme qui trouve la somme de certains intervalles avec $ O (1) $. Le prétraitement coûte $ O (N) $. Définissez une séquence $ \ {s_n \} $ qui satisfait $ s_0 = 0, s_i = \ sum_ {k = 0} ^ {i-1} a_k $ pour la séquence $ \ {a_n \} $ .. Autrement dit, $ s_i $ est la somme de $ [0, i) $. La somme de $ [a, b) $ est calculée par $ s_b-s_a $.

python

a = [i for i in range(11)]
s = [0]
for i in a:
    s.append(s[-1] + i)
print(s[3] - s[0]) # 0 + 1 + 2 = 3
print(s[11] - s[8]) # 8 + 9 + 10 = 27

Combinaison / commande

Obtenez le nombre total

Le Python d'Atcoder est la version 3.4.3 (au 31 décembre 2019), vous ne pouvez donc pas utiliser scipy.special.perm () dans le module scipy, mais vous pouvez utiliser scipy.misc.comb (). .. Je veux utiliser scipy parce que c'est rapide. </ del> (Ajouté le 19 mai 2020) Le Python d'Atcoder a été mis à jour vers la version 3.8.2! Utilisons scipy.special!

python

from scipy.misc import comb
print(comb(3, 2)) # 3.0
print(comb(3, 2, exact=True)) # 3

La séquence est implémentée par vous-même.

python

from math import factorial
def perm(n, r):
    return factorial(n) // factorial(n - r)
print(perm(3, 2)) # 6

Recherche de priorité de profondeur / recherche de priorité de largeur (en cours d'édition)

Les deux recherchent en énumérant les états possibles. La manière de chercher est différente. Pyon Diary [Competition Pro Memorandum: Depth Priority Search, Width Priority Search Summary](https://pyteyon.hatenablog.com/entry/2019/03 / 01/211133) a été utilisée comme référence.

Recherche de priorité de profondeur

Imaginez un arbre avec des racines. Recherchez en ligne droite de la racine à la feuille à la fin.

1. Commencez à partir de l'état initial
2. Transition en ligne droite vers l'endroit où vous pouvez aller
3. Lorsque vous atteignez le point où vous pouvez aller en 2., retournez une transition et effectuez la transition de là à l'endroit où vous pouvez aller.
4. Répétez les étapes 2 et 3 pour énumérer les états

Mettez en œuvre le processus ci-dessus. L'important est

• Clarifier les conditions de résiliation ―― Pensez à l'état actuel et à la profondeur

python

def dfs（）:

Recherche de priorité de largeur

Utilisez le module deque du module collections pour implémenter la file d'attente. Vous pouvez utiliser list pour recréer la file d'attente, mais il en coûte $ O (n) $ pour calculer pop (0) ʻet ʻinsert (1, n). D'un autre côté, avec deque, ces calculs peuvent être effectués avec $ O (1) $. Assurez-vous de l'utiliser.