Tips (data structure) that you should know when programming competitive programming with Python2

The part about the data structure of tips you should know when programming competitive programming with Python2 has been divided.

The Python version is ** 2.7.5 ** (Python3 has very different specifications such as input / output, so it is recommended to refer to other articles).

int

Integer type.

Strictly speaking, Python integers include integer type int and long integer type long.

For that reason, you don't have to worry too much.

Convert a string to an integer

print int('10') # 10

I like this area because it's very concise.

Radix conversion

Radix conversion of integers frequently occurs in process computers.

@ n_knuu6 taught me.

By using format (), it is possible to convert from a decimal number to a character string expressed in 2/8/16.

#Binary number
b = format(10, 'b') # '1010'

#8 base
o = format(10, 'o') # '12'

#Hexadecimal(Lowercase)
x = format(10, 'x') # 'a'

#Hexadecimal(uppercase letter)
X = format(10, 'X') # 'A'

On the contrary, if you want to convert a character string expressed in 2/8/16 decimal number to a decimal number, specify the radix of the original character string in the second argument of ʻint () `.

d1 = int('1010', 2) # 10
d2 = int('12', 8) # 10
d3 = int('a', 16) # 10
d4 = int('A', 16) # 10

Bit operation

I will write it someday.

float

Floating point type.

Convert a string to floating point

print float('10.00') # 10.0

What to do if the result of division is floating point

The following points are often addicted to floating point relationships.

#The remainder of the division is truncated
a = 5 / 2 # 2

If the result of division between integers is a non-integer value, the result is truncated (Python 3 seems to solve this problem).

If you want to correctly represent the division between integers,

a1 = 5 * 1.0 / 2 # 2.5
a2 = 5. / 2 # 2.5
a3 = float(5) / 2 # 2.5

As shown in, either the numerator or denominator should be a float type.

Handle infinity

Infinity, often used in competitive programming.

Of course, it is possible to set a very large integer value such as 10000000000 as infinity, but depending on the input value, it may exceed the set value, which causes an unexpected bug.

In Python, float ('inf') can represent infinity.

p_inf = float('inf') #Positive infinity
print p_inf > 10000000000 # True
print p_inf + 10000000000 # inf
print p_inf - 10000000000 # inf
print min(10000000000, float('inf')) # 10000000000

n_inf = -float('inf') #Negative infinity
print n_inf < -10000000000 # True

print float('inf') - float('inf') # nan
print float('inf') / float('inf') # nan
print float('inf') * 0 # nan

Note that the value becomes nan (indefinite) when subtracting or dividing between infinities or multiplying infinity by 0 as described above.

str

Character string type. Note that you cannot change the character string (reassign it to the elements that make up the character string) as in Java.

Outputs a string in reverse order

I use it very often (but forget it soon).

s = 'abc'
reverse = s[::-1] # 'cba'

Conversion of a string and a list of each character in the string

This is also often used.

s = 'abc'
l = list(s) # ['a', 'b', 'c']

ns = ''.join(l) # 'abc'
ns2 = ','.join(l) # 'a,b,c'

#By the way, str(l)Is not an inverse operation
bad = str(l) # "['a', 'b', 'c']"

Get ASCII code from alphanumeric characters

In competitive programming, ASCII codes are often obtained from characters (the famous one is Caesar cipher).

c = 'a'
print ord('a') # 97

#Error if you add a character string of 2 or more characters or a character that cannot be represented by ASCII code to the argument
print ord('ab') # TypeError

list

So-called arrays (strictly speaking, Python also has an array module, so it's a mistake, but unless you need a lot of speedup, use a list). There are various functions.

5. Data Structures — Python 2.7ja1 documentation

List-Create, Extract, Replace, Add, Search, Delete, Number of Elements-Memo

The basics are written on the above page, so they are omitted.

Initialization

If the number of elements is small, you can substitute it as it is, but for example, in C ++

int a[100][100];

What to do with something like that.

One-dimensional list initialization

There are initialization by list comprehension notation and initialization by \ *.

#Both are lists with 100 consecutive 0s([0, 0, ..., 0])To the variable l
l = [0 for i in range(100)] #Initialization using list comprehension notation
l = [0] * 100 # *Initialization using

By the way, when comparing the execution time using% timeit of ipython,

In [45]: %timeit [0] * 1000000
100 loops, best of 3: 6.66 ms per loop

In [46]: %timeit [0 for i in range(1000000)]
10 loops, best of 3: 65.1 ms per loop

Therefore, it was found that the initialization using * is faster.

2D list initialization

Here, in order to generate a two-dimensional list of 10 \ * 10,

l = [[0] * 10] * 10

Is wrong. If you use \ * for a list, the list reference will be copied, so

l = [[0] * 10] * 10
l[0][0] = 1
print l
# [[1, 0, 0, ..., 0],
#  [1, 0, 0, ..., 0],
#  ...
#  [1, 0, 0, ..., 0]]

As shown, the change spreads to other parts. This is a rather addictive place.

Correctly,

l = [[0] * 10 for i in range(10)]
l[0][0] = 1
print l
# [[1, 0, 0, ..., 0],
#  [0, 0, 0, ..., 0],
#  ...
#  [0, 0, 0, ..., 0]]

Or

l = [[0 for j in range(10)] for i in range(10)]

Let. The same applies to 3D and above.

When I benchmarked the execution time for this as well,

In [40]: %timeit [[0] * 1000 for i in range(1000)]
100 loops, best of 3: 7.04 ms per loop

In [42]: %timeit [[0 for j in range(1000)] for i in range(1000)]
10 loops, best of 3: 48 ms per loop

It turned out that it seems better to use \ * where it can be used.

List comprehension

5. Data Structures — Python 2.7ja1 documentation

Python list comprehension-comparing to how to write Ruby and Haskell | A memo for forgetting the brain soon

A unique Python notation for operating on lists.

It seems that the learning cost is a little high for the Python language specification, but I think it's worth remembering because it allows simple and powerful expressions.

As mentioned in the above example, it should be used instead of map () and filter ().

l = range(5) # [0, 1, 2, 3, 4]
x = [2 * e for e in l if e >= 3] #Extract only 3 or more elements of l(filter), Returns a set of doubles it as a list(map)
print x # [6, 8]

Also applicable to multidimensional lists.

l = [[0] * 10 for i in range(10)]
x = [[e + 1 for e in l[i]] for i in range(len(l))] #Add 1 to all elements of the list
print l
# [[1, 1, ..., 1],
#  [1, 1, ..., 1],
#  ...
#  [1, 1, ..., 1]]

You can also write a short for loop. List comprehensions are generally faster.

l = []
for i in range(10):
    for j in range(10):
        l.append((i, j))
print l
# [(0, 0),
#  (0, 1),
#  (0, 2),
#  ...
#  (9, 8),
#  (9, 9)]

#The above code can be written in one line
print [(i, j) for i in range(10) for j in range(10)]

Nesting is possible as shown below, but it is not recommended because it is often complicated.

l = range(5) # [0, 1, 2, 3, 4]
x = [e for e in [2 * e for e in l if e >= 3] if e > 7] #Of the elements of l, only 3 or more are taken out, and only those larger than 7 are returned as a list for the set of doubled elements.
print x # [8]

sort

There is a non-destructive sorted () function and a destructive sort () method.

Both sorted () and sort () are sorted in ascending order by default, but can be changed to descending order by passing reverse = True as an argument.

If the element to be sorted is a character string, it will be sorted in lexicographic order.

l = [5, 1, 3, 4, 2]

print sorted(l) # [1, 2, 3, 4, 5]
print l # [5, 1, 3, 4, 2]
print l.sort() # None
print l # [1, 2, 3, 4, 5]

l.sort(reverse=True)
print l # [5, 4, 3, 2, 1]

If each element of the list is a tuple, by default, the 0th element of each element is sorted, and then the 1st element is sorted for the same value, and so on.

l2 = [('hoge', 1), ('fuga', 3), ('piyo', 2), ('fuga', 1)]

print sorted(l2) # [('fuga', 1), ('fuga', 3), ('hoge', 1), ('piyo', 2)]

Sorting by specifying a key is also possible by giving key =" lambda expression " as an argument.

l2 = [('hoge', 1), ('fuga', 3), ('piyo', 2), ('fuga', 1)]

#For l2, the following two are equivalent
print sorted(l2) # [('fuga', 1), ('fuga', 3), ('hoge', 1), ('piyo', 2)]
print sorted(l2, key=lambda x: (x[0], x[1])) # [('fuga', 1), ('fuga', 3), ('hoge', 1), ('piyo', 2)]

#The second element is sorted in descending order, and those with the same value are sorted in ascending order for the first element.
print sorted(l2, key=lambda x: (-x[1], x[0]) # [('fuga', 3), ('piyo', 2), ('fuga', 1), ('hoge', 1)]

set and dict

I will write it someday.

Stack / queue

In Python, the list object acts as a stack and queue.

l = [0, 1, 2, 3]

# push/enque
l.append(4)
print l # [0, 1, 2, 3, 4]

# pop
x = l.pop() # 4
print l # [0, 1, 2, 3]

# deque
y = l.pop(0) # 0
print l # [1, 2, 3]

** Addendum: ** Thank you to @wonderful_panda.

8.3. collections — High Performance Container Data Types — Python 2.7ja1 documentation

ʻAppend ()andpop ()are $ O (1) $, butpop (0)` is an operation of $ O (n) $, so if the number of elements in the list increases, it will take time to deque. It will be like this. When using (stack,) queues, it is safe to use collections.deque.

from collections import deque

l = [0, 1, 2, 3]
q = deque(l)

# push/enque
q.append(4)
print q # deque([0, 1, 2, 3, 4])

# pop
x = q.pop() # 4
print q # deque([0, 1, 2, 3])

# deque
y = q.popleft() # 0
print q # deque([1, 2, 3])

Priority queue

Implemented Dijkstra's algorithm in Python-Don't call it futu!

Priority queue (priority queue) that is taken care of in competitive programming.

I wrote an article on my blog before, so please refer to that.

Recommended Posts

Tips (data structure) that you should know when programming competitive programming with Python2
Tips (control structure) that you should know when programming competitive programming with Python2
Tips you should know when programming competitive programming with Python2
Tips (input / output) that you should know when programming competitive programming with Python2
Tips you should know when programming competitive programming with Python2 (useful library)
Knowledge you need to know when programming competitive programming with Python2
Tips to know when programming competitively with Python2 (Other language specifications)
Competitive programming with python
Knowledge of linear algebra that you should know when doing AI
Competitive programming with python Local environment settings
I made a competitive programming glossary with Python
Create test data like that with Python (Part 1)
Personal tips when doing various things with Python 3
[python] [vscode] When you get angry with space-tab-mixed
Solve with Python [100 past questions that beginners and intermediates should solve] (053 --055 Dynamic programming: Others)
You should know if you use Python! 10 useful libraries
What are you using when testing with Python?
All the destructive methods that data scientists should know
A server that echoes data POSTed with flask / python
Directory structure when writing tests with Python 3 standard unittest
Data analysis with python 2
3. 3. AI programming with Python
Competitive programming diary python 20201213
Python programming with Atom
Competitive programming diary python 20201220
[Python tutorial] Data structure
Competitive programming diary python
Data analysis with Python
[Tips] Dealing with errors that occur when trying to install Python 3 series less than 3.5.3 with pyenv
If you want to use field names with hyphens when updating firestore data in python
Solution when you want to use cv_bridge with python3 (virtualenv)
A memo that reads data from dashDB with Python & Spark
Use a macro that runs when saving python with vscode
Solve the spiral book (algorithm and data structure) with python!
When you want to register Django's initial data with relationships
Xpath summary when extracting data from websites with Python Scrapy
Programming with Python and Tkinter
I tried to find out as much as possible about the GIL that you should know if you are doing parallel processing with Python
[Tips] Handle Athena with Python
Error when playing with python
Network programming with Python Scapy
Data processing tips with Pandas
Read json data with python
If you know Python, you can make a web application with Django
Let's create a Python directory structure that you won't regret later
What should I do with the Python directory structure after all?
Introduction of "scikit-mobility", a library that allows you to easily analyze human flow data with Python (Part 1)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (039 --045 Dynamic programming: Knapsack DP variant)