I have listed the algorithms that can be used in competition pros.
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
'''
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])
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))
Here article is easy to understand I will implement it soon ...
Recommended Posts