Basic algorithms that can be used in competition pros

What article?

I have listed the algorithms that can be used in competition pros.

* Updated from time to time

Primality test (Eratosthenes sieve)

https://atcoder.jp/contests/abc084/tasks/abc084_d


from itertools import accumulate
import math
m = 10**5

L = [x for x in range(2,m+1)]

#Extract prime numbers with a sieve of Eratosthenes
for y in range(2, int(math.sqrt(m)+1)):
    L = [z for z in L if(z == y or z % y != 0)]

#N+1/Extract what 2 is also a prime number
P = []
for w in L:
    if (w+1)/2 in L:
        P.append(w)

#Created for cumulative sum
G = [0] * (m+1)
for i in P:
    G[i+1] = 1

#Cumulative sum
Q = list(accumulate(G))



n = int(input())
for _ in range(n):
    s, t = map(int, input().split())
    print(Q[t+1]-Q[s])




'''
The following primality tests are slow.
Use an Eratosthenes sieve as above

def isPrime(n):

    if n == 1:
        return False
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)+1), 2):
        if n % i == 0:
            return False
    return True

'''

Bit dynamic programming (traveling salesman problem)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A

v, e = map(int, input().split())

inf = 10**7
edges = [[inf]*v for _ in range(v)]

for i in range(e):
    s, t, d = map(int, input().split())
    edges[s][t] = d

#Dp is the minimum cost in S when the order is optimized under the constraint that the subset S of the whole set ends with v.
dp = [[inf]*v for _ in range(2**v)]
dp[0][0] = 0

#Set (binary number indicating whether visited or not)
for x in range(2**v):
    #Last visited node
    for y in range(v):
        #Nodes other than the last visited
        for z in range(v):
            #1.Whether you have already visited 2.Isn't it the last node visited 3.Are y and z connected in the first place?
            if ((x >> y) & 1) and y != z and edges[z][y] < 10**6:
                dp[x][y] = min(dp[x][y], dp[x^(1<<y)][z]+edges[z][y])

if dp[-1][0] > 10**6:
    print(-1)
else:
    print(dp[-1][0])

Shortest path problem (Bellman-Ford algorithm)

I referred to here. Also, the explanation about Bellman-Ford was easy to understand in the article here.


#v:Vertex e:Edge
v, e = map(int, input().split())
#List to store edges (neither adjacency matrix nor adjacency list)
edges = []

for _ in range(e):
    s, t, w = map(int, input().split())
    edges.append([s, t, w])
    # edges.append([t, s, w])

#Less than,Bellmanford
def bellman_ford(start,goal,edges,v):
    #Distance initialization
    distance = [float("inf")] * v
    distance[start] = 0
    
    for i in range(v):
        #Whether the distance has been updated
        updated = False
        for s, t, w in edges:
            if distance[t] > distance[s] + w:
                distance[t] = distance[s] + w
                updated = True
        #Evidence that the shortest path is found when the distance is no longer updated
        if not updated:
            break
        #The update of the shortest path does not end even after updating v times → There is a negative cycle
        if i == v - 1:
            return -1
    return distance[goal]

for i in range(v):
    print(bellman_ford(0, i, edges, v))

Maximum flow problem (Ford-Fulkerson)

Here article is easy to understand I will implement it soon ...

Recommended Posts

Basic algorithms that can be used in competition pros
Can be used in competition pros! Python standard library
Python standard input summary that can be used in competition pro
Functions that can be used in for statements
ANTs image registration that can be used in 5 minutes
Goroutine (parallel control) that can be used in the field
Goroutine that can be used in the field (errgroup.Group edition)
Scripts that can be used when using bottle in Python
A timer (ticker) that can be used in the field (can be used anywhere)
Easy padding of data that can be used in natural language processing
Acoustic signal processing module that can be used with Python-Sounddevice ASIO [Basic]
File types that can be used with Go
Building Sphinx that can be written in Markdown
Utilization of recursive functions used in competition pros
A personal memo of Pandas related operations that can be used in practice
Easy program installer and automatic program updater that can be used in any language
I made a familiar function that can be used in statistics with Python
Linux command that can be used from today if you know it (Basic)
Japanese can be used with Python in Docker environment
Python knowledge notes that can be used with AtCoder
[Django] About users that can be used on template
Summary of statistical data analysis methods using Python that can be used in business
Basic knowledge of DNS that can not be heard now
Text analysis that can be done in 5 minutes [Word Cloud]
Evaluation index that can be specified in GridSearchCV of sklearn
List of my articles that may be useful in competition pros (updated from time to time)
[Django] Field names, user registration, and login methods that can be used in the User model
[Python3] Code that can be used when you want to resize images in folder units
I made it because I want JSON data that can be used freely in demos and prototypes
[Python] Basic knowledge used in AtCoder
Make a Spinbox that can be displayed in Binary with Tkinter
33 strings that should not be used as variable names in python
About character string handling that can be placed in JSON communication
New features in Python 3.9 (1)-Union operators can be used in dictionary types
Confirmation that rkhunter can be installed
Make a Spinbox that can be displayed in HEX with Tkinter
Python standard module that can be used on the command line
I wrote a tri-tree that can be used for high-speed dictionary implementation in D language and Python.
About the matter that the re.compiled object can be used for the re.match pattern
Acoustic signal processing module that can be used with Python-Sounddevice ASIO [Application]
Hide the warning that zsh can be used by default on Mac
Serverless LINE Bot that can be done in 2 hours (source identifier acquisition)
Mathematical optimization that can be used for free work with Python + PuLP
Maximum number of function parameters that can be defined in each language
A story that heroku that can be done in 5 minutes actually took 3 days
[Python3] Code that can be used when you want to cut out an image in a specific size
QPS control that can be used in the field (Rate Limit) Limits execution to n times per second
[2015.02.22] Youtube-dl has been updated and can no longer be used in previous versions.
I want to create a priority queue that can be updated in Python (2.7)
If "can not be used when making a PIE object" appears in make
Summary of scikit-learn data sources that can be used when writing analysis articles
How to install a Python library that can be used by pharmaceutical companies
It can be achieved in 1 minute! Decorator that caches function execution results in memcached
"Gazpacho", a scraping module that can be used more easily than Beautiful Soup
List of tools that can be used to easily try sentiment analysis of Japanese sentences in Python (try with google colab)
++ and-cannot be used for increment / decrement in python
Until youtube-dl can be used with Synology (DS120j)
List packages that can be updated with pip
The problem that the ifconfig command cannot be used
Overview and useful features of scikit-learn that can also be used for deep learning
Convert images from FlyCapture SDK to a form that can be used with openCV