Vielen Dank. Ich werde den Schreibstil zusammenfassen, der dem Wettbewerbsprofi eigen ist, den ich (@ rainline00) brauchte, um die früheren Fragen des Atcoder Begginers Contest mit Python zu lösen. Ich werde es von Zeit zu Zeit hinzufügen.
index
[Eingabe](# Eingabe) [List Element Search](#List Element Search)
[Alle durchsuchen](# Alle durchsuchen) [Maximales Versprechen / minimales gemeinsames Vielfaches](# maximales Versprechen minimales gemeinsames Vielfaches) [Kumulative Summe](#Kumulative Summe) [Kombination / Reihenfolge](# Kombinationsreihenfolge) [Tiefenprioritätssuche / Breitenprioritätssuche](# Tiefenprioritätssuche Breitenprioritätssuche)
Es ist leicht, die ganzen Zahlen zu vergessen, die einzeln in n Zeilen eingegeben werden.
python
s = input() #String
n = int(input()) #Integer Wert
a, b = map(int, input().split()) #Zwei oder mehr ganze Zahlen
li = list(map(int, input().split())) #list
li2 = [int(input()) for _ in range(n)] #Eine Ganzzahl, die nacheinander in n Zeilen eingegeben wird
list.index (n) gibt nur einen Index mit übereinstimmenden Werten zurück. Gibt mehrere Werte in einer Liste unter Verwendung der Listeneinschlussnotation zurück.
python
li = [0, 2, 1, 4, 2, 3, 2]
indexes = [i for i, x in enumerate(li) if x == 2] #Suche nach 2
print(indexes) # [1, 4, 6]
Wenn Sie alle Fälle wie "verwenden oder nicht verwenden" für jede Variable aufzählen können ($ O (2 ^ N) $ ist ausreichend), können Sie die Bit-Vollsuche verwenden. Die Gesamtzahl der Ziffern, die "Verwendung oder Nichtverwendung" darstellen, wird durch die Anzahl der Variablen ermittelt. Es kann nur durch eine Binärzahl dargestellt werden.
Listen Sie alle $ 2 ^ n $ -Zustände "Kaufen oder nicht kaufen" für jedes Nachschlagewerk auf und stellen Sie fest, ob die Bedingungen erfüllt sind. Durch die Verwendung von "Array" von "Numpy" kann es schnell und präzise beschrieben werden.
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)
Wenn das maximale und minimale gemeinsame Vielfache mehrerer Variablen gefunden wird, kann es mit der übergeordneten Funktion redu () rekursiv geschrieben werden.
Die Python von atcoder ist Version 3.4.3 (Stand 31. Dezember 2019). Verwenden Sie daher das Modul "Brüche" anstelle des Moduls "Mathematik". </ del>
(Hinzugefügt am 19. Mai 2020) Atcoder's Python wurde auf 3.8.2 aktualisiert! Verwenden wir das Modul 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)
Ein Algorithmus, der die Summe bestimmter Intervalle mit $ O (1) $ ermittelt. Die Vorverarbeitung kostet $ O (N) $. Definieren Sie eine Sequenz $ \ {s_n \} $, die $ s_0 = 0, s_i = \ sum_ {k = 0} ^ {i-1} a_k $ für die Sequenz $ \ {a_n \} $ erfüllt .. Das heißt, $ s_i $ ist die Summe von $ [0, i) $. Die Summe von $ [a, b) $ wird durch $ s_b-s_a $ berechnet.
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
Atcoders Python ist Version 3.4.3 (Stand 31. Dezember 2019), daher können Sie "scipy.special.perm ()" nicht im "scipy" -Modul verwenden, sondern "scipy.misc.comb ()". .. Ich möchte scipy verwenden, weil es schnell ist. </ del>
(Hinzugefügt am 19. Mai 2020) Atcoder's Python wurde auf 3.8.2 aktualisiert! Verwenden wir scipy.special!
python
from scipy.misc import comb
print(comb(3, 2)) # 3.0
print(comb(3, 2, exact=True)) # 3
Die Sequenz wird von Ihnen selbst implementiert.
python
from math import factorial
def perm(n, r):
return factorial(n) // factorial(n - r)
print(perm(3, 2)) # 6
Beide suchen durch Aufzählung möglicher Zustände. Die Art der Suche ist anders. pyon diary [Competition pro Memorandum: Suche nach Tiefenpriorität, Zusammenfassung der Suche nach Breitenpriorität](https://pyteyon.hatenablog.com/entry/2019/03 / 01/211133) wurde als Referenz verwendet.
Stellen Sie sich einen Baum mit Wurzeln vor. Suchen Sie in einer geraden Linie von der Wurzel bis zum Blatt am Ende.
Implementieren Sie den obigen Prozess. Wichtig ist
python
def dfs（）:
Verwenden Sie die "Deque" des "Collections" -Moduls, um die Warteschlange zu implementieren. Sie können "list" verwenden, um die Warteschlange zu reproduzieren, aber die Berechnung von "pop (0)" und "insert (1, n)" kostet $ O (n) $. Andererseits können diese Berechnungen mit "deque" mit $ O (1) $ durchgeführt werden. Stellen Sie sicher, dass Sie dies verwenden.
Recommended Posts