Tips you should know when programming competitive programming with Python2 (useful library)

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.

Set of math functions math

I will write it someday.

Itertools for permutations, combinations, etc.

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

Counter useful for creating counters

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

Recommended Posts

Tips you should know when programming competitive programming with Python2 (useful library)
Tips you should know when programming competitive programming with Python2
Tips (input / output) that you should know when programming competitive programming with Python2
Tips (control structure) that you should know when programming competitive programming with Python2
Tips (data structure) that you should know when programming competitive programming with Python2
Knowledge you need to know when programming competitive programming with Python2
Tips to know when programming competitively with Python2 (Other language specifications)
Competitive programming with python
You should know if you use Python! 10 useful libraries
I made a competitive programming glossary with Python
[python] [vscode] When you get angry with space-tab-mixed
What are you using when testing with Python?
BigQuery-Python was useful when working with BigQuery from Python
3. 3. AI programming with Python
Competitive programming diary python 20201213
Python programming with Atom
Competitive programming diary python 20201220
Competitive programming diary python
Programming with Python Flask
I know? Data analysis using Python or things you want to use when you want with numpy
Useful operation when you want to solve all problems in multiple programming languages with Codewars
Solution when you want to use cv_bridge with python3 (virtualenv)
Until you can install your own Python library with pip
Programming with Python and Tkinter
Useful when debugging with TouchDesigner
[Tips] Handle Athena with Python
Python Competitive Programming Site Summary
Error when playing with python
Network programming with Python Scapy
If you know Python, you can make a web application with Django
Knowledge of linear algebra that you should know when doing AI
Python3 standard input for competitive programming
Competitive programming, coding test template: Python3
Nice to meet you with python
[Python] Object-oriented programming learned with Pokemon
Easy Python + OpenCV programming with Canopy
[Hyperledger Iroha] Query with Python library
Until you run python with apache
When matplotlib doesn't work with python2.7
When using MeCab with virtualenv python
Precautions when using six with Python 2.5
[VS Code] ~ Tips when using python ~
Python | What you can do with Python
[Python] Format when to_csv with pandas
What Emacs users should know when writing python code in Sublime Text