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.

Recommended Posts

A collection of competitive pro techniques to solve with Python
Solve A ~ D of yuki coder 247 with python
Try to solve a set problem of high school math with Python
A memo connected to HiveServer2 of EMR with python
Solve ABC163 A ~ C with Python
Solve ABC166 A ~ D with Python
Solve ABC168 A ~ C with Python
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Solve ABC158 A ~ C with Python
Can be used with AtCoder! A collection of techniques for drawing short code in Python!
I tried to create a list of prime numbers with python
I wanted to solve the ABC164 A ~ D problem with Python
I wanted to solve ABC160 with Python
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
I wanted to solve ABC172 with Python
[Introduction to Python] How to sort the contents of a list efficiently with list sort
A beginner of machine learning tried to predict Arima Kinen with python
How to read a CSV file with Python 2/3
Send a message to LINE with Python (LINE Notify)
I made a competitive programming glossary with Python
I wanted to solve NOMURA Contest 2020 with Python
Try to solve the man-machine chart with Python
Try to draw a life curve with python
I want to make a game with Python
Try to make a "cryptanalysis" cipher with Python
How to specify attributes with Mock of python
Decide to assign a laboratory with Python (fiction)
Steps to create a Twitter bot with python
I want to solve APG4b with Python (Chapter 2)
Try to make a dihedral group with Python
I want to write to a file with Python
A layman wants to get started with Python
Try to solve the traveling salesman problem with a genetic algorithm (Python code)
I tried to make a simple mail sending application with tkinter of Python
Competitive Pro with Python and VSCode-Simplification of standard input and automation of sample case judgment-
How to get a list of files in the same directory with python
[Introduction to Python] How to get the index of data with a for statement
Solve AtCoder 167 with python
Competitive Pro Template (Python)
Solve Sudoku with Python
Competitive programming with python
Solve POJ 2386 with python
How to convert / restore a string with [] in python
Try to solve the programming challenge book with python3
[Python] How to draw a line graph with Matplotlib
Recommendation of building a portable Python environment with conda
Try to make a command standby tool with python
Try to solve the internship assignment problem with Python
I tried to draw a route map with Python
Change IP settings to ACL of conoha with python
I tried to solve the soma cube with python
[Chapter 5] Introduction to Python with 100 knocks of language processing
How to write a list / dictionary type of Python3
I want to work with a robot in python.
From buying a computer to running a program with python
[Chapter 3] Introduction to Python with 100 knocks of language processing
I tried to automatically generate a password with Python3
Python + selenium to GW a lot of e-mail addresses
[Python] A memo to write CSV vertically with Pandas