Use Python 3rd Algorithm Practical Test
The algorithm practice test is a competitive programming (algorithm power) test provided by AtCoder. PAST is an abbreviation for Practical Algorithm Skill Test. googleability is a little bad.
It usually costs 8800 yen / person (tax included), but the 3rd time is free. The normal AtCoder rating is a relative evaluation color display, but in PAST there are 5 levels of absolute evaluation. All 15 questions are 5 hours, so 20 minutes per question.
With a 1GHz CPU, you can roughly execute a loop 10 ^ 9 times in 1s. The time limit for execution depends on the time, but it is about 2s. Python is about 1/10 faster than C ++, and if it is a simple loop, it will be executed a little faster by optimization, but in any case, if it exceeds 10 ^ 10, it will not finish in time.
Comparison in lowercase letters. 3 characters x 2 is a moment, so it has nothing to do with the amount of calculation.
#!/bin/python3
import sys
input = sys.stdin.readline
def main():
s = input().strip()
t = input().strip()
if s == t:
print("same")
elif s.lower() == t.lower():
print("case-insensitive")
else:
print("different")
main()
The point that each person can get is not fixed when the problem is solved, and when another person solves the problem, the points are deducted retroactively.
Honestly, if you update the score array for max 10 ^ 5 people every time in a loop of queries with max 10 ^ 5, it will not end at 10 ^ 10. You can reduce the amount of calculation by writing down the score of the problem and the problem you solved.
#!/bin/python3
import sys
input = sys.stdin.readline
from collections import defaultdict
def print_score(score, solved, n):
result = 0
for i in solved[n]:
result += score[i]
print(result)
def solve_problem(score, solved, n, m):
solved[n].append(m)
score[m] -= 1
def main():
n, m, q = list(map(int, input().strip().split()))
score = [n]*m
solved = defaultdict(list)
for i in range(q):
query = list(map(int, input().strip().split()))
if query[0] == 1:
print_score(score, solved, query[1]-1)
elif query[0] == 2:
solve_problem(score, solved, query[1]-1, query[2]-1)
main()
If you apply it honestly, the calculation of 10 ^ 9 times will not be completed, so it will be terminated when it becomes large to some extent.
Depending on the language, there seems to be a technique to discontinue the calculation if N> = 31 by utilizing the fact that 2 ^ 30> 10 ^ 9 due to overflow.
#!/bin/python3
import sys
input = sys.stdin.readline
def main():
a, r, n = list(map(int, input().strip().split()))
v = a
LIMIT = 10**9
for _ in range(n-1):
v *= r
if v > LIMIT:
print('large')
sys.exit()
print(v)
main()
Since the example is each character of 0-9, just use it to parse. Since it is 50 (N) x width 4 x column 5, the calculation ends in time. It is easier to implement if you think that each of the width 4 including the non-display part corresponds to each number rather than considering only the display part.
#!/bin/python3
import sys
input = sys.stdin.readline
def main():
n = int(input().strip())
s = []
for i in range(5):
s.append(input().strip())
num = ['.###..#..###.###.#.#.###.###.###.###.###',
'.#.#.##....#...#.#.#.#...#.....#.#.#.#.#',
'.#.#..#..###.###.###.###.###...#.###.###',
'.#.#..#..#.....#...#...#.#.#...#.#.#...#',
'.###.###.###.###...#.###.###...#.###.###']
board = []
for i in range(10):
tmp = []
for j in range(5):
tmp.append(num[j][4*i:4*i+4])
board.append(tmp)
result = ''
for k in range(n):
for i in range(10):
count = 0
for j in range(5):
if board[i][j] == s[j][4*k:4*k+4]:
count += 1
else:
break
if count == 5:
result += str(i)
break
print(result)
main()
At first I thought that sprinklers would always be running and the colors would propagate, but that's not the case. Overwrite the color of nearby nodes only at startup.
It is difficult to find the adjacent node from the list of adjacent pairs later, so make a note of the adjacent node of a certain node first.
#!/bin/python3
import sys
input = sys.stdin.readline
from collections import defaultdict
def print_color(c, x):
print(c[x])
def launch_sprinkler(c, vdict, x):
for i in vdict[x]:
c[i] = c[x]
def change_color(c, x, y):
c[x] = y
def main():
n, m, q = list(map(int, input().strip().split()))
vdict = defaultdict(list)
for i in range(m):
u, v = list(map(int, input().strip().split()))
vdict[u-1].append(v-1)
vdict[v-1].append(u-1)
c = list(map(int, input().strip().split()))
for i in range(q):
query = list(map(int, input().strip().split()))
if query[0] == 1:
print_color(c, query[1]-1)
launch_sprinkler(c, vdict, query[1]-1)
elif query[0] == 2:
print_color(c, query[1]-1)
change_color(c, query[1]-1, query[2])
main()
At first I thought it was a palindrome when I was deceived by the example and cut out in the column direction, but it is not. A palindrome created when one character is taken from each line
If there is a product of the set of each row on the head side and the set of each row on the buttock, save one appropriately. Palindrome generation is divided into cases where the column length is odd-numbered and even-numbered.
#!/bin/python3
import sys
input = sys.stdin.readline
from collections import defaultdict
def main():
n = int(input().strip())
a = []
for i in range(n):
a.append(set(list(input().strip())))
s = []
for i in range(n//2):
common = list(a[i] & a[-i-1])
if len(common) > 0:
s.append(common[0])
else:
print(-1)
sys.exit()
if n % 2 == 0:
print(''.join(s + s[::-1]))
else:
print(''.join(s + [list(a[n//2])[0]] + s[::-1]))
main()
Shortest path problem. It seems that it can be solved with BFS, but with Dijkstra. Obstacles may be lined up in a straight line like a wall in an infinitely wide area, so it is necessary to set a wider place for movement than the place where obstacles can be placed.
Since it was troublesome to express that I could not reach, I used a large enough number for places that I could not pass.
#!/bin/python3
import sys
input = sys.stdin.readline
from collections import defaultdict
# n:Number of vertices
# g[v] = {(w, cost)}:
#Vertices that can be transitioned from vertex v(w)And its cost(cost)
# s:The apex of the starting point
from heapq import heappush, heappop
INF = float("inf")
def dijkstra(n, g, s):
dist = [INF] * n
que = [(0, s)]
dist[s] = 0
while que:
c, v = heappop(que)
if dist[v] < c:
continue
for t, cost in g[v]:
if dist[v] + cost < dist[t]:
dist[t] = dist[v] + cost
heappush(que, (dist[t], t))
return dist
def main():
n, x, y = list(map(int, input().strip().split()))
x = x + 210
y = y + 210
weight = [[1] * 420 for i in range(420)]
move = [(1,1), (0,1), (-1,1), (1,0), (-1,0), (0,-1)]
for i in range(n):
a, b = list(map(int, input().strip().split()))
a += 210
b += 210
weight[a][b] = 10000
g = defaultdict(list)
for i in range(5, 415):
for j in range(5, 415):
for a,b in move:
pos = 420*(i+a)+j+b
cost = weight[i+a][j+b]
g[420*i+j].append((pos, cost))
start = 420*210+210
dist = dijkstra(1700*1700, g, start)
end = 420*x+y
result = dist[end]
if result >= 10000:
print(-1)
else:
print(result)
main()
Most people solve it with pure dynamic programming. But with Dijkstra. It needs to be corrected because the arrival is judged at the timing of passing.
#!/bin/python3
import sys
input = sys.stdin.readline
from collections import defaultdict
# n:Number of vertices
# g[v] = {(w, cost)}:
#Vertices that can be transitioned from vertex v(w)And its cost(cost)
# s:The apex of the starting point
from heapq import heappush, heappop
INF = float("inf")
def dijkstra(n, g, s):
dist = [INF] * n
que = [(0, s)]
dist[s] = 0
while que:
c, v = heappop(que)
if dist[v] < c:
continue
for t, cost in g[v]:
if dist[v] + cost < dist[t]:
dist[t] = dist[v] + cost
heappush(que, (dist[t], t))
return dist
def main():
n, l = list(map(int, input().strip().split()))
x = list(map(int, input().strip().split()))
t = list(map(int, input().strip().split()))
board = [0] * (l+5)
for i in x:
board[i] = 1
g = defaultdict(list)
for i in range(l):
for j in range(3):
if j == 0:
pos = i+1
cost = t[0]
elif j == 1:
pos = i+2
cost = t[0] + t[1]
if pos > l:
pos = l
cost = (t[0] + t[1])/2
else:
pos = i+4
cost = t[0] + t[1] * 3
if pos > l:
pos = l
cost = t[0]*0.5 + t[1]*0.5 + t[1]*(l-i-1)
if board[i] == 1:
cost += t[2]
g[i].append((pos, round(cost)))
start = 0
dist = dijkstra(l+5, g, start)
end = l
result = dist[end]
print(result)
main()
When the NxN array is rearranged, it does not finish in time at 10 ^ 10. For transposition, it is OK if the rows and columns are swapped and the rows and columns are swapped at the next reference. If you create a conversion array to replace rows and columns, you do not need to actually modify the matrix.
Also, if the NxN matrix is initialized as a two-dimensional array, it will be 10 ^ 5 * 10 ^ 5 = 10 ^ 10, so it is necessary to calculate it when printing at the end.
import sys
input = sys.stdin.readline
from collections import defaultdict
def replace_column(convert_column, a, b):
tmp_a = convert_column[a]
tmp_b = convert_column[b]
convert_column[a] = tmp_b
convert_column[b] = tmp_a
def replace_row(convert_row, a, b):
tmp_a = convert_row[a]
tmp_b = convert_row[b]
convert_row[a] = tmp_b
convert_row[b] = tmp_a
def print_matrix(n, a, b):
print(n*a+b)
def main():
n = int(input().strip())
q = int(input().strip())
convert_column = []
for i in range(n):
convert_column.append(i)
convert_row = []
for i in range(n):
convert_row.append(i)
transpose = False
for i in range(q):
query = list(map(int, input().strip().split()))
if query[0] == 1:
if transpose:
replace_column(convert_column, query[1]-1, query[2]-1)
else:
replace_row(convert_row, query[1]-1, query[2]-1)
elif query[0] == 2:
if transpose:
replace_row(convert_row, query[1]-1, query[2]-1)
else:
replace_column(convert_column, query[1]-1, query[2]-1)
elif query[0] == 3:
transpose = not transpose
elif query[0] == 4:
if transpose:
print_matrix(n, convert_row[query[2]-1], convert_column[query[1]-1])
else:
print_matrix(n, convert_row[query[1]-1], convert_column[query[2]-1])
main()
https://github.com/hiromichinomata/atcoder
Recommended Posts