Utilisez Python 3e test pratique de l'algorithme
Le test d'habileté pratique de l'algorithme est un test de programmation de compétition (puissance d'algorithme) fourni par AtCoder. PAST est une abréviation de Practical Algorithm Skill Test. la googleability est un peu mauvaise.
Il coûte généralement 8800 yens / personne (taxes incluses), mais la 3ème fois est gratuite. La notation AtCoder normale est un affichage couleur d'évaluation relative, mais dans PAST, il existe 5 niveaux d'évaluation absolue. Les 15 questions durent 5 heures, donc 20 minutes par question.
Avec un processeur à 1 GHz, vous pouvez à peu près exécuter une boucle 10 ^ 9 fois en 1s. Le délai d'exécution dépend du sujet, mais il est d'environ 2 secondes. Python est environ 1/10 plus rapide que C ++, et s'il s'agit d'une simple boucle, il sera exécuté un peu plus vite par optimisation, mais dans tous les cas, s'il dépasse 10 ^ 10, il ne se terminera pas à temps.
Comparaison en minuscules.3 caractères x 2 sont instantanés, donc cela n'a rien à voir avec la quantité de calcul.
#!/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()
Les points que chaque personne peut obtenir ne sont pas fixés lorsque le problème est résolu, et lorsque d'autres personnes résolvent le problème, les points sont déduits rétroactivement.
Honnêtement, si vous mettez à jour le tableau de score pour un maximum de 10 ^ 5 personnes à chaque fois dans une boucle de 10 ^ 5 requêtes maximum, il ne se terminera pas à 10 ^ 10. Vous pouvez réduire la quantité de calcul en notant le score du problème et le problème que vous avez résolu.
#!/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()
Si vous l'appliquez honnêtement, le calcul de 10 ^ 9 fois ne sera pas terminé, il sera donc coupé lorsqu'il deviendra important dans une certaine mesure.
Selon la langue, il semble y avoir une technique pour interrompre le calcul si N> = 31 en utilisant le fait que 2 ^ 30> 10 ^ 9 en raison d'un débordement.
#!/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()
Puisque l'exemple est chaque caractère de 0 à 9, utilisez-le simplement pour analyser. Comme il est de 50 (N) x largeur 4 x colonne 5, le calcul se termine dans le temps. Il est plus facile à mettre en œuvre si l'on pense que chacune des largeurs 4 incluant la partie non d'affichage correspond à chaque nombre plutôt que de ne considérer que la partie d'affichage.
#!/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()
Au début, je pensais que les arroseurs fonctionneraient toujours et que les couleurs se propageraient, mais ce n'est pas le cas. Remplacez la couleur des nœuds voisins uniquement au démarrage.
Il est difficile de trouver le nœud adjacent dans la liste des paires adjacentes plus tard, alors notez d'abord le nœud adjacent d'un certain nœud.
#!/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()
Au début, je pensais que c'était une circulaire lorsque j'ai été trompé par l'exemple et découpé dans le sens de la colonne, mais ce n'est pas le cas. Une transcription qui peut être faite lorsqu'un caractère est extrait de chaque ligne
S'il y a un produit de l'ensemble de chaque rangée du côté de la tête et de l'ensemble de chaque rangée du côté inférieur, enregistrez-en un de manière appropriée. La génération circulaire est divisée en cas où la longueur de la colonne est une longueur impaire et une longueur paire.
#!/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()
Problème d'itinéraire le plus court. Il semble que cela puisse être résolu avec BFS, mais avec Dyxtra. Les obstacles peuvent être alignés en ligne droite comme un mur dans une zone infiniment large, il est donc nécessaire de définir un lieu de mouvement plus large que celui où les obstacles peuvent être placés.
Comme il était difficile d'exprimer que je ne pouvais pas atteindre, j'ai utilisé un nombre assez grand pour les endroits que je ne pouvais pas passer.
#!/bin/python3
import sys
input = sys.stdin.readline
from collections import defaultdict
# n:Nombre de sommets
# g[v] = {(w, cost)}:
#Un sommet qui peut être transféré du sommet v(w)Et son coût(cost)
# s:Le sommet du point de départ
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()
La plupart des gens le résolvent avec une planification dynamique pure. Mais avec Dyxtra. Il doit être corrigé car il est jugé qu'il arrive au moment du passage.
#!/bin/python3
import sys
input = sys.stdin.readline
from collections import defaultdict
# n:Nombre de sommets
# g[v] = {(w, cost)}:
#Un sommet qui peut être transféré du sommet v(w)Et son coût(cost)
# s:Le sommet du point de départ
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()
Lorsque la séquence NxN est réorganisée, elle ne se termine pas à temps à 10 ^ 10. Pour la translocation, c'est OK si les lignes et les colonnes sont échangées et les lignes et les colonnes sont échangées à la référence suivante. Si vous créez un tableau de conversion, vous n'avez pas besoin de modifier la matrice pour changer de ligne et de colonne.
De plus, si la matrice NxN est initialisée comme un tableau à deux dimensions, elle sera 10 ^ 5 * 10 ^ 5 = 10 ^ 10, il est donc nécessaire de la calculer lors de l'impression à la fin.
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