A collection of competitive pro techniques to solve with Python

What kind of article

Thanks. I will summarize the writing style peculiar to the competition pro that I (@ rainline00) needed in the process of solving the past questions of Atcoder Begginers Contest with python. I will add it from time to time.

index

How to write

[Input](# input) [List Element Search](#List Element Search)

Algorithm related

[Full Search](# Full Search) [Greatest common divisor / least common multiple](# greatest common divisor / least common multiple) [Cumulative sum](#Cumulative sum) [Combination / Permutation](#Combination permutation) [Depth-first search / Breadth-first search](#Depth-first search Width-first search)

input

It's easy to forget the integers that are entered one by one in n lines.

python

s = input() #String
n = int(input()) #Integer value
a, b = map(int, input().split()) #Two or more integers
li = list(map(int, input().split())) #list
li2 = [int(input()) for _ in range(n)] #Integer entered one by one in n lines

List element search

list.index (n) returns only one index with matching values. Returns multiple values in a list using list comprehension notation.

python

li = [0, 2, 1, 4, 2, 3, 2] 
indexes = [i for i, x in enumerate(li) if x == 2] #Search for 2
print(indexes) # [1, 4, 6]

Full search

bit full search

If it is enough to enumerate all the cases such as "use or not use" for each variable (when $ O (2 ^ N) $ is enough), bit full search can be used. The total number of digits representing "use or not use" is taken by the number of variables. It can be represented by only one binary number.

Example: ABC167C --Skill Up

List all the $ 2 ^ n $ states of "buy or not buy" in each reference book and judge whether the conditions are met. You can write it quickly and concisely by using ʻarray of numpy`.

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)

Greatest common divisor / least common multiple

To find the greatest common divisor and least common multiple of multiple variables, it can be written recursively using the higher-order function reduce (). Atcoder's python is version 3.4.3 (as of December 31, 2019), so use the fractions module instead of the math module. </ del> (Added on May 19, 2020) Atcoder's Python has been updated to 3.8.2! Let's use the math module

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)

Cumulative sum

An algorithm that finds the sum of certain intervals with $ O (1) $. Preprocessing costs $ O (N) $. Define a sequence $ \ {s_n \} $ that satisfies $ s_0 = 0, s_i = \ sum_ {k = 0} ^ {i-1} a_k $ for the sequence $ \ {a_n \} $ .. That is, $ s_i $ is the sum of $ [0, i) $. The sum of $ [a, b) $ is calculated by $ s_b-s_a $.

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

Combination / Permutation

Get the total number

Atcoder's Python is Version 3.4.3 (as of December 31, 2019), so you can't use scipy.special.perm () in the scipy module, but you can usescipy.misc.comb (). .. I want to use scipy because it's fast. </ del> (Added on May 19, 2020) Atcoder's Python has been updated to 3.8.2! Let's use scipy.special!

python

from scipy.misc import comb
print(comb(3, 2)) # 3.0
print(comb(3, 2, exact=True)) # 3

Implement the permutation yourself.

python

from math import factorial
def perm(n, r):
    return factorial(n) // factorial(n - r)
print(perm(3, 2)) # 6

Depth-first search / breadth-first search (editing)

Both search by enumerating possible states. The way of searching is different. py Tyon Diary's [Competition Pro Memorandum: Depth-first Search, Breadth-First Search Summary](https://pyteyon.hatenablog.com/entry/2019/03 / 01/21 1133) was used as a reference.

Depth-first search

Imagine a tree with roots. Search in a straight line from the root to the leaf at the end.

1. Start from the initial state
2. Transition in a straight line to where you can go
3. When you reach the point where you can go in step 2, return one transition and make the transition from there to where you can go.
4. Repeat steps 2 and 3 to enumerate the states

Implement the above process. The important thing is

--Clarify the termination conditions ――Think about the current state and depth

python

def dfs（）:

Breadth-first search

Use the deque of the collections module to implement the queue. You can use list to recreate the queue, but it costs $ O (n) $ to calculatepop (0)and ʻinsert (1, n). On the other hand, with deque`, those calculations can be done with $ O (1) $. Be sure to use this.