Can be used in competition pros! Python standard library

Introduction

--Introducing the Python standard library that can be used in competitive programming. --It also contains AtCoder problems and code that were actually solved using the Python standard library. --The version of Python 3 in AtCoder is 3.4.3. --I will not explain the problem.

Standard library

bisect ** Array dichotomy algorithm **

bisect_left(a, x, lo=0, hi=len(a))

Returns the position where $ x $ can be inserted into $ a $ for the sorted list $ a $. If $ a $ contains $ x $, the insertion point will be before (left) any existing $ x $ value.

bisect_right(a, x, lo=0, hi=len(a)) Similar to bisect_left (), but if $ a $ contains $ x $, the insertion point will be after (right) any existing $ x $ value.

from bisect import bisect_left, bisect_right

a = [1, 2, 2, 2, 3, 5]
print(bisect_left(a, 2))  # -> 1
print(bisect_right(a, 2))  # -> 4

** Problem example **

heapq ** Heap Queue Algorithm / Priority Queue Algorithm **

heappush(heap, item)

Push item to heap.

heappop(heap)

Returns the smallest element from the heap.

from heapq import heappop, heappush

a = []
heappush(a, (10, 'x'))
heappush(a, (5, 'y'))
heappush(a, (1, 'z'))

print(a)  # -> [(1, 'z'), (10, 'x'), (5, 'y')]
print(heappop(a))  # -> (1, 'z')
print(heappop(a))  # -> (5, 'y')
print(heappop(a))  # -> (10, 'x')

collections ** Container data type **

deque A list-like container that allows fast append and pop at both ends. appendleft () and poplift () can be achieved faster than equivalent operations on list.

from collections import deque

q = deque(['a', 'b', 'b', 'b', 'd', 'd'])
print(q.popleft())  # -> a
print(q)  # -> deque(['b', 'b', 'b', 'd', 'd'])
q.appendleft('z')
print(q)  # -> deque(['z', 'b', 'b', 'b', 'd', 'd'])

Counter

A subclass of a dictionary that counts hashable objects. To count the number of one element, you can use the count () method of list or tuple, but it is convenient when counting the number of all elements.

from collections import Counter

l = ['a', 'b', 'b', 'b', 'd', 'd']
t = ('a', 'b', 'b', 'b', 'd', 'd',)
print(l.count('b'))  # -> 3
print(t.count('b'))  # -> 3
c = Counter(l)
print(c)  # -> Counter({'b': 3, 'd': 2, 'a': 1})
#Returns all elements in descending order of count
print(c.most_common())  # -> [('b', 3), ('d', 2), ('a', 1)]

ABC008 B Voting Code

itertools ** Iterator generation function for efficient loop execution **

product(*iterables, repeat)

Returns the Cartesian product of multiple iterables.

from itertools import product

l = ['a', 'b', 'c']
m = ['x', 'y']
print(list(product(l, m)))
# -> [('a', 'x'), ('a', 'y'), ('b', 'x'), ('b', 'y'), ('c', 'x'), ('c', 'y')]

permutations(iterable, r)

Returns a permutation of length r from the element of iterable.

from itertools import permutations

l = ['a', 'b', 'c']
print(list(permutations(l, 3)))
# -> [('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]
print(list(permutations(l, 2)))
# -> [('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]

combinations(iterable, r) Returns the combination when selecting r from the elements of iterable.

from itertools import combinations

l = ['a', 'b', 'c', 'd', 'e']
print(list(combinations(l, 2)))
# -> [('a', 'b'), ('a', 'c'), ('a', 'd'), ('a', 'e'), ('b', 'c'), ('b', 'd'), ('b', 'e'), ('c', 'd'), ('c', 'e'), ('d', 'e')]

** Problem example ** ABC123 A Five Antennas Code

functools ** Manipulating higher-order functions and callable objects **

lru_cache(maxsize, typed) A decorator that wraps a function in a callable object for memoization. Save up to maxsize recent calls. It can be used in memoization recursion.

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib(n):
	if n < 2:
		return n
	return fib(n - 1) + fib(n - 2);
 
print(fib(100))  # -> 354224848179261915075
print(fib.cache_info())  # -> CacheInfo(hits=98, misses=101, maxsize=None, currsize=101)

reduce(function, iterable[, initializer])

Iterable elements are cumulatively applied from the left to a function that takes two arguments, and the result is returned.

from functools import reduce

def f(a, b):
	return a * b

l = [1, 2, 3, 4, 5]
# ((((1 * 2) * 3) * 4) * 5)Equivalent to
print(reduce(f, l))  # -> 120

fractions ** Rational number **

gcd(a, b) Returns the greatest common divisor of the integers $ a $ and $ b $.

If you want to find the least common multiple, implement lcm as follows.

from fractions import gcd

def lcm(a, b):
    return a*b // gcd(a, b)

** Problem example ** ABC070 C Multiple Clocks Code

Extra edition

Introducing built-in functions that can be used in competition pros.

pow() ** Exponentiation **

$ pow (x, y [, z]) $ returns the remainder of $ z $ for $ x \ ^ y $ or $ x \ ^ y $. By using this, the inverse element of $ a $ in $ mod $$ p $ can be calculated by $ pow (a, p-2, p) $.

It can be used to find the remainder of $ p $, which is the number of combinations to select $ k $ from $ n $.

def nCk(n, k, p):
    ret = 1
    for i in range(k):
        ret = ret * (n - i) * pow(i + 1, p - 2, p) % p
    return ret

** Problem example ** ABC034 C route Code

Recommended Posts

Can be used in competition pros! Python standard library
Python standard input summary that can be used in competition pro
Basic algorithms that can be used in competition pros
[Redash] Standard library cannot be used in python function
Japanese can be used with Python in Docker environment
Scripts that can be used when using bottle in Python
New features in Python 3.9 (1)-Union operators can be used in dictionary types
Python standard module that can be used on the command line
Functions that can be used in for statements
Utilization of recursive functions used in competition pros
Standard .py file used in Python trials (template)-2020
I made a familiar function that can be used in statistics with Python
How to install a Python library that can be used by pharmaceutical companies
Python knowledge notes that can be used with AtCoder
list comprehension because operator.methodcaller cannot be used in python 2.5
Operators ++,-cannot be used in python (difference from php)
Non-linear simultaneous equations can be easily solved in Python.
Summary of statistical data analysis methods using Python that can be used in business
Python3 standard input (competition pro)
[Python] Frequently used library code
Overriding library functions in Python
Transposed matrix in Python standard
How to debug the Python standard library in Visual Studio
What you can do with the Python standard library statistics
Goroutine (parallel control) that can be used in the field
Goroutine that can be used in the field (errgroup.Group edition)
SSD 1306 OLED can be used with Raspberry Pi + python (Note)
[Python3] Code that can be used when you want to resize images in folder units
What seems to be a template of the standard input part of the competition pro in python3
[Python] I made my own library that can be imported dynamically
8 Frequently Used Commands in Python Django
About psd-tools, a library that can process psd files in Python
[Python] Basic knowledge used in AtCoder
Make standard output non-blocking in Python
33 strings that should not be used as variable names in python
A timer (ticker) that can be used in the field (can be used anywhere)
Windows10: Install MeCab library in python
I wrote a tri-tree that can be used for high-speed dictionary implementation in D language and Python.
Easy padding of data that can be used in natural language processing
I created a template for a Python project that can be used universally
Mathematical optimization that can be used for free work with Python + PuLP
[Python, Julia] 3D display in Jupyter-Mayavi library
[python] Frequently used techniques in machine learning
What is "mahjong" in the Python library? ??
Tkinter could not be imported in Python
Python standard library: second half (Python learning memo ⑨)
Python standard library: First half (Python learning memo ⑧)
[Python3] Code that can be used when you want to cut out an image in a specific size
[2015.02.22] Youtube-dl has been updated and can no longer be used in previous versions.
I want to create a priority queue that can be updated in Python (2.7)
I registered PyQCheck, a library that can perform QuickCheck with Python, in PyPI.
A personal memo of Pandas related operations that can be used in practice
Easy program installer and automatic program updater that can be used in any language
Get all standard inputs used in paiza and competitive programming with int (python)
List of tools that can be used to easily try sentiment analysis of Japanese sentences in Python (try with google colab)
How to use the C library in Python
Until youtube-dl can be used with Synology (DS120j)
File types that can be used with Go
How to use Python Image Library in python3 series
Techniques often used in python short coding (Notepad)
Notes on using dict in python [Competition Pro]