The part about the library of tips you should know when programming competitive programming with Python2 has been divided.
The Python version is ** 2.7.5 ** (Python3 has very different specifications such as input / output, so it is recommended to refer to other articles).
Here are some libraries that I find useful, though they are a little minor.
I will write it someday.
9.7. itertools — Iterator generation function for efficient loop execution
Use itertools to get combinations and permutations in Python | CUBE SUGAR STORAGE
A library packed with methods to generate iterators.
In competitive programming, it is useful when generating permutations and combinations (corresponding to next_permutation in C ++). It operates much faster than turning multiple loops by yourself, so you should actively use it.
permutations.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Select two elements from l and arrange them
#Do not consider duplication
#Order is considered(permutation)
for elem in itertools.permutations(l, 2):
print elem #The tuple of the arranged elements is assigned to elem
output
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 1)
(2, 3)
(2, 4)
(2, 5)
(3, 1)
(3, 2)
(3, 4)
(3, 5)
(4, 1)
(4, 2)
(4, 3)
(4, 5)
(5, 1)
(5, 2)
(5, 3)
(5, 4)
combinations.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Select 3 elements from l and arrange them
#Do not consider duplication
#Does not consider the order(combination)
for elem in itertools.combinations(l, 3):
print elem
output
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)
By the way, combinations that take duplication into consideration and Cartesian products (direct products) can also be obtained.
combinations_with_replacement.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Arrange the two sets of the extracted elements of l
#Consider duplication
#Does not consider the order
for elem in itertools.product(l, repeat=2):
print elem
output
(1, 1)
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 2)
(2, 3)
(2, 4)
(2, 5)
(3, 3)
(3, 4)
(3, 5)
(4, 4)
(4, 5)
(5, 5)
cartesian_product.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Arrange the two sets of the extracted elements of l
#Consider duplication
#Order is considered
for elem in itertools.product(l, repeat=2):
print elem
#The above code is equivalent to the following code
for a in l:
for b in l:
print (a, b)
output
(1, 1)
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(2, 5)
(3, 1)
(3, 2)
(3, 3)
(3, 4)
(3, 5)
(4, 1)
(4, 2)
(4, 3)
(4, 4)
(4, 5)
(5, 1)
(5, 2)
(5, 3)
(5, 4)
(5, 5)
collections
8.3. collections — High Performance Container Data Types — Python 2.7ja1 documentation
Python collections module is sober and convenient-materialistic @Scaled_Wurm
defaultdict
As the name implies, collections.defaultdict is a dict with default values.
In competitive programming, there are many opportunities to create counters (especially in implementation game problems).
For example, when a question is asked about the frequency of English words existing in the input, it is necessary to create a counter corresponding to each word using dict, but dict initializes the key. Otherwise, an error will occur, which is troublesome.
By using defaultdict, you can reduce initialization and make the code easier to read.
from collections import defaultdict
l = ['to', 'be', 'or', 'not', 'to', 'be', 'that', 'is', 'the', 'question']
#For dict
d = {}
for e in l:
#Check if there is a key value every time, if not, you need to initialize
if e in d.keys():
d[e] += 1
else:
d[e] = 1
print d # {'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2}
dd = defaultdict(int) #All keys are initialized with 0
for e in l:
dd[e] += 1 #No need to initialize
print dd # defaultdict(<type 'int'>, {'be': 2, 'that': 1, 'is': 1, 'question': 1, 'to': 2, 'not': 1, 'the': 1, 'or': 1})
print dd['be'] # 2
dd2 = defaultdict(list) #All keys[]Initialized with
dd2['a'].append(1)
print dd2 # defaultdict(<type 'list'>, {'a': [1]})
collections.Counter is an object specialized for counter creation, and 0 is automatically set as the initial value.
This is equivalent to defautdict (int), but there are some other useful functions such as finding the maximum value immediately.
from collections import Counter
l = ['to', 'be', 'or', 'not', 'to', 'be', 'that', 'is', 'the', 'question']
c = Counter()
for e in l:
c[e] += 1
print c # Counter({'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2})
print c['be'] # 2
#If you pass a list etc. as an argument, it will be counted automatically
c2 = Counter(l)
print c2 # Counter({'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2})
#Sorted in descending order of counter values
print c.most_common() # [('be', 2), ('to', 2), ('that', 1), ('is', 1), ('question', 1), ('not', 1), ('the', 1), ('or', 1)]
#Outputs 3 in order from the one with the largest counter value
print c.most_common(3) # [('be', 2), ('to', 2), ('that', 1)]