Verwenden Sie Python 3. Algorithmus-Praxistest
Der praktische Fähigkeitstest für Algorithmen ist ein von AtCoder bereitgestellter Test zur Programmierung von Wettbewerben (Algorithmusleistung). PAST ist eine Abkürzung für Practical Algorithm Skill Test. googleability ist ein wenig schlecht.
Es kostet normalerweise 8800 Yen / Person (inklusive Steuern), aber das 3. Mal ist kostenlos. Die normale AtCoder-Bewertung ist eine relative Bewertungsfarbanzeige, aber in PAST gibt es 5 Stufen der absoluten Bewertung. Alle 15 Fragen sind 5 Stunden, also 20 Minuten pro Frage.
Mit einer 1-GHz-CPU können Sie eine Schleife ungefähr 10 ^ 9 Mal in 1s ausführen. Das Zeitlimit für die Ausführung hängt von der Angelegenheit ab, beträgt jedoch ungefähr 2 Sekunden. Python ist ungefähr 1/10 schneller als C ++, und wenn es sich um eine einfache Schleife handelt, wird es durch Optimierung etwas schneller ausgeführt. Wenn es jedoch 10 ^ 10 überschreitet, wird es nicht rechtzeitig beendet.
Vergleich in Kleinbuchstaben: 3 Zeichen x 2 sind augenblicklich, haben also nichts mit dem Rechenaufwand zu tun.
#!/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()
Die Punkte, die jede Person erhalten kann, werden nicht behoben, wenn das Problem gelöst ist, und wenn andere Personen das Problem lösen, werden die Punkte rückwirkend abgezogen.
Ehrlich gesagt, wenn Sie das Score-Array für maximal 10 ^ 5 Personen jedes Mal in einer Abfrage-Schleife mit maximal 10 ^ 5 aktualisieren, endet es nicht bei 10 ^ 10. Sie können den Rechenaufwand reduzieren, indem Sie die Punktzahl des Problems und das von Ihnen gelöste Problem aufschreiben.
#!/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()
Wenn Sie es ehrlich anwenden, wird die Berechnung von 10 ^ 9-mal nicht abgeschlossen, so dass es abgeschnitten wird, wenn es zu einem gewissen Grad groß wird.
Abhängig von der Sprache scheint es eine Technik zu geben, die Berechnung abzubrechen, wenn N> = 31 ist, indem die Tatsache genutzt wird, dass 2 ^ 30> 10 ^ 9 aufgrund eines Überlaufs.
#!/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()
Da das Beispiel jedes Zeichen von 0-9 ist, verwenden Sie es einfach zum Parsen. Da es 50 (N) x Breite 4 x Spalte 5 ist, endet die Berechnung mit der Zeit. Es ist einfacher zu implementieren, wenn Sie der Meinung sind, dass jede der Breiten 4 einschließlich des nicht angezeigten Teils jeder Zahl entspricht, anstatt nur den angezeigten Teil zu berücksichtigen.
#!/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()
Zuerst dachte ich, dass Sprinkler immer laufen würden und sich die Farben ausbreiten würden, aber das ist nicht der Fall. Überschreiben Sie die Farbe benachbarter Knoten nur beim Start.
Es ist schwierig, den benachbarten Knoten später aus der Liste der benachbarten Paare zu finden. Notieren Sie sich daher zuerst den benachbarten Knoten eines bestimmten Knotens.
#!/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()
Zuerst dachte ich, es sei ein Rundschreiben, als ich durch das Beispiel getäuscht und in Spaltenrichtung ausgeschnitten wurde, aber das ist es nicht. Eine Transkription, die erstellt werden kann, wenn aus jeder Zeile ein Zeichen entnommen wird
Wenn sich ein Produkt aus dem Satz jeder Reihe auf der Kopfseite und dem Satz jeder Reihe auf der Unterseite befindet, speichern Sie eines entsprechend. Die Kreisgenerierung ist in Fälle unterteilt, in denen die Spaltenlänge ungerade und gerade Länge ist.
#!/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()
Problem mit der kürzesten Route. Es scheint, dass es mit BFS gelöst werden kann, aber mit Dyxtra. Hindernisse können in einer geraden Linie wie eine Wand in einem unendlich weiten Bereich ausgerichtet sein. Daher muss ein breiterer Bewegungsort festgelegt werden, als Hindernisse platziert werden können.
Da es schwierig war auszudrücken, dass ich nicht erreichen konnte, benutzte ich eine ausreichend große Anzahl für Orte, die ich nicht passieren konnte.
#!/bin/python3
import sys
input = sys.stdin.readline
from collections import defaultdict
# n:Anzahl der Eckpunkte
# g[v] = {(w, cost)}:
#Ein Scheitelpunkt, der vom Scheitelpunkt v überführt werden kann(w)Und seine Kosten(cost)
# s:Die Spitze des Startpunktes
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()
Die meisten Leute lösen es mit rein dynamischer Planung. Aber mit Dyxtra. Es muss korrigiert werden, da beurteilt wird, dass es zum Zeitpunkt des Bestehens kommt.
#!/bin/python3
import sys
input = sys.stdin.readline
from collections import defaultdict
# n:Anzahl der Eckpunkte
# g[v] = {(w, cost)}:
#Ein Scheitelpunkt, der vom Scheitelpunkt v überführt werden kann(w)Und seine Kosten(cost)
# s:Die Spitze des Startpunktes
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()
Wenn die NxN-Sequenz neu angeordnet wird, endet sie nicht rechtzeitig um 10 ^ 10. Für die Translokation ist es in Ordnung, wenn die Zeilen und Spalten ausgetauscht werden und die Zeilen und Spalten bei der nächsten Referenz ausgetauscht werden. Wenn Sie ein Konvertierungsarray erstellen, müssen Sie die Matrix nicht ändern, um Zeilen und Spalten zu ersetzen.
Wenn die NxN-Matrix als zweidimensionales Array initialisiert wird, beträgt sie 10 ^ 5 * 10 ^ 5 = 10 ^ 10, sodass sie beim Drucken am Ende berechnet werden muss.
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