I tried to summarize what python strong people are doing in the competition professional neighborhood

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.

What I did first

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)

Actual code

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

Output related

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

Input related

#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.

Commonly used libraries

Next, I tried to identify the frequently used libraries.

Array related

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.

data structure

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)

dictionary

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')

Summary

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

I tried to summarize what python strong people are doing in the competition professional neighborhood
[Python] I tried to summarize the set type (set) in an easy-to-understand manner.
I tried to graph the packages installed in Python
I tried to summarize how to use pandas in python
I tried to summarize the string operations of Python
I tried to summarize the new coronavirus infected people in Ichikawa City, Chiba Prefecture
I tried to summarize the code often used in Pandas
I tried to summarize the commands often used in business
I tried to implement the mail sending function in Python
I tried to summarize Python exception handling
I tried to implement PLSA in Python
I tried to summarize the umask command
I tried to implement permutation in Python
I tried to implement PLSA in Python 2
Python3 standard input I tried to summarize
I tried to summarize the graphical modeling.
I tried to implement ADALINE in Python
I tried to implement PPO in Python
I tried to summarize the contents of each package saved by Python pip in one line
[At Coder] What I did to reach the green rank in Python
I tried to summarize the methods that are often used when implementing basic algo in Quantx Factory
I tried to summarize all the Python plots used in the research by active science graduate students [Basic]
I tried simulating the "birthday paradox" in Python
I tried the least squares method in Python
I tried to implement TOPIC MODEL in Python
I tried to implement selection sort in python
LeetCode I tried to summarize the simple ones
I want to display the progress in Python!
I want to visualize where and how many people are in the factory
I tried to summarize the operations that are likely to be used with numpy-stl
I tried to implement what seems to be a Windows snipping tool in Python
I tried to summarize all the Python visualization tools used in research by active science graduate students [Application]
I tried to summarize how to use matplotlib of python
I tried to summarize the basic form of GPLVM
I tried to touch the CSV file with Python
I tried to solve the soma cube with python
I tried to implement a pseudo pachislot in Python
I tried to implement Dragon Quest poker in Python
I tried to implement GA (genetic algorithm) in Python
[Python] I tried to graph the top 10 eyeshadow rankings
I want to write in Python! (3) Utilize the mock
I tried to solve the problem with Python Vol.1
I want to use the R dataset in python
Python OpenCV tried to display the image in text.
[LPIC 101] I tried to summarize the command options that are easy to make a mistake
[Series for busy people] I tried to summarize by parsing to call news in 30 seconds
[For beginners in competition professionals] I tried to solve 40 AOJ "ITP I" questions with python
[Python] I tried to summarize the array, dictionary generation method, loop method, list comprehension notation
I tried to make a function to judge whether the major stock exchanges in the world are daylight saving time with python
I tried to find the entropy of the image with python
I tried to simulate how the infection spreads with Python
[First COTOHA API] I tried to summarize the old story
I tried the accuracy of three Stirling's approximations in python
I tried to create API list.csv in Python from swagger.yaml
I tried to implement a one-dimensional cellular automaton in Python
What I did to welcome the Python2 EOL with confidence
I tried "How to get a method decorated in Python"
I tried to illustrate the time and time in C language
I tried programming the chi-square test in Python and Java.
[Python] I tried to visualize the follow relationship of Twitter
What seems to be a template of the standard input part of the competition pro in python3