AtCoder ABC 176 Python (A ~ E)

Zusammenfassung

A, B, C gelöst. Ich denke, D und E können in etwas mehr Zeit gelöst werden, aber ich konnte sie zum Zeitpunkt des Wettbewerbs nicht lösen, und es wurde zu einem späteren Zeitpunkt AC.

Problem

https://atcoder.jp/contests/abc176

A. Takoyaki

Antworten

N, X, T = map(int, input().split())

if N % X == 0:
    ans = (N // X) * T
else:
    ans = (N // X) * T + T

print(ans)

Die Fälle wurden danach unterteilt, ob die Anzahl N des herzustellenden Takoyaki ein Vielfaches von X ist oder nicht, was die maximale Kapazität der Takoyaki-Maschine darstellt.

B. Multiple of 9

Antworten

N = list(str(input()))

total = 0
for i in range(len(N)):
    total += int(N[i])

if total % 9 == 0:
    print('Yes')
else:
    print('No')

Zur Problemstellung

"Die ganze Zahl N ist ein Vielfaches von 9, und die Summe der Zahlen in jeder Ziffer, wenn N dezimal ausgedrückt wird, ist ein Vielfaches von 9."

Da er einen Hinweis geschrieben hat, werde ich ihn so wie er ist in den Code einfügen. Benötigten Sie diesen Hinweis nicht? Ich dachte.

C. Step

Antworten

N = int(input())
A = list(map(int, input().split()))

total = 0
for i in range(N-1):
    if A[i] > A[i+1]:
        diff = A[i] - A[i+1]
        total += diff
        A[i+1] += diff

print(total)

Vergleichen Sie das aktuelle A [i] mit dem nächsten A [i + 1], und wenn A [i + 1] größer ist, addieren Sie die Differenz.

Das C-Problem war einfach, daher befürchtete ich, dass es vor dem Einreichen einige Fallstricke geben könnte, und ich dachte, dass es etwas geben könnte, da der Maximalwert von A, der eine Einschränkung darstellt, 10 ** 9 beträgt. Ich habe versucht, es vorerst zu löschen, und es ist vorbei.

D. Wizard in Maze

Antwort (Ich werde es zu einem späteren Zeitpunkt mit AC Pypy weitergeben. Python ist TLE)

#---------------------------------[importieren]---------------------------------#
from collections import deque
#---------------------------------[Eingangsempfang / Grundeinstellung]---------------------------------#
H, W = map(int, input().split())
C = tuple(map(int, input().split())) #Magische Position
D = tuple(map(int, input().split())) #Tor
D_y = D[0] -1 #0 Start
D_x = D[1] -1 #0 Start
S = [list(input()) for _ in range(H)]
visited = [[-1] * W for _ in range(H)]
visited[C[0]-1][C[1]-1] = 0 #Ursprünglicher Wert
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] #Gewöhnliche Bewegung
main_q = deque()
magic_q = deque() #Stichwort für Magie
main_q.append((C[0]-1, C[1]-1))
#---------------------------------[BFS]---------------------------------#
while main_q:
    y, x = main_q.popleft()
    magic_q.append((y, x))
    for move in moves:
        dy, dx = move
        moved_y = y + dy
        moved_x = x + dx

        if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
            continue
        if S[moved_y][moved_x] == '#':
            continue
        if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
            main_q.append((moved_y, moved_x))
            visited[moved_y][moved_x] = visited[y][x]
    #---------------------------------[BFS für Magie]---------------------------------#
    if not main_q: # main_Wenn q leer wird, verwenden Sie Magie von gesucht
        while magic_q:
            y, x = magic_q.popleft()
            for dy in range(-2, 3):
                for dx in range(-2, 3):
                    moved_y = y + dy
                    moved_x = x + dx

                    if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
                        continue
                    if S[moved_y][moved_x] == '#':
                        continue
                    if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
                        main_q.append((moved_y, moved_x))
                        visited[moved_y][moved_x] = visited[y][x] + 1
#---------------------------------[Antwortanzeige]---------------------------------#
answer = visited[D_y][D_x]
print(answer)

In dem Moment, als ich das Problem las, dachte ich, ich könnte es nicht mit BFS lösen, aber ich konnte es beim Wettbewerb nicht lösen, weil ich es mit Magie nicht gut umsetzen konnte.

Die Politik ist

1. Bewegen Sie sich zuerst normal mit Zug A (Implementieren Sie hier das erste BFS).
2. Nachdem Sie alle Bewegungen A ausgeführt haben, versuchen Sie Bewegung B mit Magie an der von Bewegung A gesuchten Stelle (gespeichert in `` `magic_q```) (Implementieren Sie hier das zweite BFS).
3. Beginnen Sie erneut mit Bewegung A von der Position, die mit Bewegung B gesucht wurde (gespeichert in `` `main_q```).
4. Wiederholen Sie die Schritte 1 bis 3 unten. Notieren Sie beim Bewegen, wie oft Magic in "besucht" verwendet wurde
5. Die Häufigkeit, mit der das Ziel "besucht" aufgezeichnet wurde, ist die Antwort Es wird sein.

Unter der Annahme, dass Sie ein normales BFS schreiben können, war der Schlüssel zu diesem Problem meiner Meinung nach, ob Sie "Aufzeichnen der Häufigkeit, mit der Magic in" besucht "verwendet wurde" implementieren konnten oder nicht.

Mit dem obigen Code wird es in Python zu TLE und Sie müssen es mit pypy übergeben. Ich denke, dass Python funktioniert, wenn Sie es entwickeln, aber ich habe es nicht verbessert, weil der Code, wie er ist, für mich leichter zu verstehen ist.

E. Bomber

Antwort (AC zu einem späteren Zeitpunkt)

import numpy as np

H, W, M = map(int, input().split())
row = np.zeros(W)
col = np.zeros(H)
memo = []
for _ in range(M):
    h, w = map(int, input().split())
    h -=1
    w -=1
    row[w] += 1
    col[h] += 1
    memo.append((h, w))

col_max = col.max()
row_max = row.max()

max_col_indexes = np.where(col == col_max)[0]
max_row_indexes = np.where(row == row_max)[0]

ans = col_max + row_max -1
memo = set(memo)
for c in max_col_indexes:
    for r in max_row_indexes:
        if (c, r) not in memo:
            ans = col_max + row_max
            print(int(ans))
            exit()

print(int(ans))

Die Richtlinie wurde sofort festgelegt und ich habe den Code angewendet, aber ich konnte den Rechenaufwand nicht reduzieren und konnte zum Zeitpunkt des Wettbewerbs keine AC durchführen.

Als Politik

1. Zählen Sie die Bomben, die in jeder Zeile und Spalte vorhanden sind, und ermitteln Sie die maximale Anzahl von Bomben (Zeile max, Spalte max) für jede Zeile und Spalte sowie die maximale Anzahl von Zeilen und Spalten.
2. Wenn Sie Bomben mit derselben Zeilennummer und Spaltennummer zählen, die maximal sind, ist `` `Zeile max + Spalte max -1``` die Antwort
3. Wenn Sie keine Bomben mit denselben Zeilen- und Spaltennummern wie max zählen, antwortet `row max + column max `
4. Um festzustellen, ob dieselben Bomben in Zeilen und Spalten gezählt werden, überprüfen Sie, ob sich Bomben mit den maximalen Koordinaten für Zeilennummer und Spaltennummer befinden. ist.

Wenn Sie nicht `memo = set (memo)` in den Code einfügen, ist dies TLE.