Nice to meet you. I'm a beginner who started the competition pro last week. I'm using python now.
If possible, I want to get good results in competition pros without relying on C ++! So I thought about how to raise the score with python.
For example in C ++
#define rep(i,n) for((i)=0;(i)<(int)(n);(i)++)
There are many people who speed up like this. In short, it feels like simplifying frequently used descriptions. I knew from before that there was such a magical custom.
However, I don't know the python version of this even though I'm doing a competition pro with python.
So, I wrote this article with the intention of learning the customs of python's strong competition professionals. I hope it will be helpful to similar people.
I read the submission code of a strong person. After all, there was a magic similar to C ++ competition pro, so I will try to decipher it. (Quoted from a certain strong person)
I will explain the actual code in order.
sys.setrecursionlimit(10 ** 6)
Sets the recursion depth of the recursive function. (default is 1000) I understand the meaning, but the necessity doesn't come to my mind.
When I looked it up, it seems that it may get caught, so I feel like setting it larger for the time being. Certainly, when an error occurs due to this, it seems difficult to notice.
Next, I found something like this.
int1 = lambda x: int(x) - 1
A function that returns the number you entered minus one. I wonder if it's up to this point ... I feel the obsession of a strong competition professional lol
p2D = lambda x: print(*x, sep="\n")
A function that displays list elements with line breaks in between. Certainly, when I did Atcoder the other day, there was a good scene with this lol
#Convert input to integer and receive
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
#Receives an array of all inputs converted to integers
def LI(): return list(map(int, sys.stdin.readline().split()))
#Receives an array of all inputs converted to integers minus 1
def LLI(rows_number): return [LI() for _ in range(rows_number)]
As a beginner, I used only input (), so first sort out the differences from readline ().
--readline () also reads the trailing newline character --input () erases the read newline character (that is, equivalent to readline (). Rstrip ())
However, since int ('1 \ n') = 1, it can be described like this. The quoted person uses readline () like this, but input () seems to be a substitute.
Next, I tried to identify the frequently used libraries.
Since pop and append of arrays are slow in python, if the answer is incorrect due to the execution time, write as follows and use the deck (double-ended queue).
from collections import deque
l = deque
l.append(1)
l.pop()
The next story about duplicating an array
#If the array is one-dimensional
list2 = list1[:]
#For 2 dimensions or more
import copy
list2 = copy.deepcopy(list1)
In the case of one dimension, if "list2 = list1" is set, list1 will be rewritten if list2 itself is rewritten because of passing by reference, so write it like this. In the case of 2D or more, deepcopy is used because it cannot be described like this.
Heaps (priority cues) are often used in competition pros. (For example, when finding the median) The heap has the following properties
--Elements can be added (pushed) and removed (pop) in O (logN) time. --Minimum value (maximum value) search can be done with O (1)
The specification is such that the minimum value comes to the apex, so if you want to bring the maximum value to the apex, multiply it by -1 and save it in the heap.
You can handle the heap as follows.
import heapq
heap = []
heapq.heappush(heap, 1)
heapq.heappop(heap)
When using a regular dictionary in python, you need to make sure that the value corresponding to the key exists. The default dict saves you such trouble. (I feel that there are many situations where I use it even if I'm not a competition professional)
Use as follows
from collections import defaultdict
d = defaultdict(int)
#To set the default when there is no key, write like this
d = defaultdict(lambda : 'Initial Value')
I think it's roughly like this, but I think there are still many things that are missing, so I plan to update it from time to time. I believe that this kind of knowledge will be useful in practice someday, and I will continue my studies.
Recommended Posts