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