--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.
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 **
Push item to 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'])
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)]
itertools ** Iterator generation function for efficient loop execution **
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')]
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
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