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
[Input](# input) [List Element Search](#List Element Search)
[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)
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.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]
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.
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)
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)
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
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
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.
Imagine a tree with roots. Search in a straight line from the root to the leaf at the end.
Implement the above process. The important thing is
--Clarify the termination conditions ――Think about the current state and depth
python
def dfs():
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