AtCoder ABC 175 Python

Zusammenfassung

ABC wurde gelöst. D und E wurden als Richtlinie eingerichtet, können jedoch nicht rechtzeitig gelöst werden. Dieses Mal konnte ich zum ersten Mal über das F-Problem nachdenken (ob es gelöst werden kann oder nicht, ist eine andere Geschichte ...) E wurde zu einem späteren Zeitpunkt gelöst, aber D konnte WA nicht vernichten und hat noch keine AC.

Problem

https://atcoder.jp/contests/abc175

A. Rainy Season

Antworten

S = tuple(input())

if S == ('R', 'R', 'R'):
    print(3)
elif S == ('R', 'R', 'S') or S == ('S', 'R', 'R'):
    print(2)
elif S == ('S', 'S', 'S'):
    print(0)
else:
    print(1)

Ich fragte mich, ob es einen guten Weg gab, es zu lösen, aber ich konnte nicht daran denken. Ich habe sie alle aufgelistet und mit einer if-Anweisung gelöst.

Zum Zeitpunkt des Wettbewerbs habe ich es in das Tupel eingefügt, aber Sie können die Zeichenkette so beurteilen, wie sie ist.

B. Making Triangle

Antworten

from itertools import combinations

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

count = 0
for C in combinations(L, 3):
    l_list = list(C)
    l_list.sort()

    if l_list[2] > l_list[1] and l_list[1] > l_list[0]:
        if l_list[2] < l_list[1] + l_list[0]:
            count += 1

print(count)

Da es sich um eine dreieckige Bedingung handelt, kann sie durch "maximale Seite <Summe der beiden anderen Seiten" gelöst werden. Da die Einschränkungen gering sind, habe ich sie alle aufgelistet.

C. Walking Takahashi

Antworten

X, K, D = map(int, input().split())

new_X = abs(X) % D
new_K = K - abs(X) // D

if new_K <= 0:
    answer = abs(X) - K*D
else:
    if new_K % 2 == 0:
        answer = new_X
    else:
        answer = abs(new_X - D)
        
print(answer)

Zunächst möchte ich die for-Anweisung definitiv nicht verwenden, da die Einschränkungen zu streng sind. Da wir eine so große Zahl verarbeiten, können wir erwarten, dass der Prozess des "Teilens einer großen Zahl durch eine Zahl" irgendwohin kommt.

In diesem Sinne möchte ich die Koordinaten `` X``` vorerst durch die zurückgelegte Strecke `Dteilen.x // d```Wenn Sie über die Bedeutung von nachdenken, können Sie sehen, dass es "die Anzahl der Bewegungen der Entfernung d ist, die erforderlich sind, um x Entfernung zurückzulegen". Wenn es um "Anzahl der Züge" geht, möchten Sie von "K" subtrahieren.

Als nächstes stellen wir beim Experimentieren mit einigen Eingabesamples fest, dass D, wenn es weit über X liegt, in der Nähe des Ursprungs vibriert. Es stellt sich heraus, dass es zwei Antworten auf Vibrationen gibt.

Zu diesem Zeitpunkt ist die Politik ziemlich solide geworden.

1. Machen Sie `` `K --X // D``` und berechnen Sie die verbleibende Anzahl von Malen
2. Da es in der Nähe des Ursprungs vibriert, teilen Sie die beiden Fälle und berechnen Sie die Antwort.
3. Achten Sie danach auf den Umgang mit Positiven und Negativen und behandeln Sie Ausnahmen, wenn X ausreichend größer als D ist.

Fügen Sie dies in Ihren Code ein.

D. Moving Piece

Antwort (Dies ist halb WA)

N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

answer = -float('inf')
for start_p in range(1, N+1):

    cycle_total_score = 0
    cycle_in_score = -float('inf')
    cycle_count = 0
    next_p = P[start_p]
    while True:
        cycle_total_score += C[next_p]
        cycle_in_score = max(cycle_in_score, cycle_total_score)
        cycle_count += 1

        if next_p == start_p:
            # print('start_p:', start_p, ' cycle_total_score:', cycle_total_score, 'cycle_in_score:', cycle_in_score, 'cycle_count:', cycle_count)
            break
        next_p = P[next_p]
    
    max_score = 0
    if K == cycle_count:
        max_score = cycle_in_score
    else:
        #Überlaufend K.% cycle_Finden Sie das Maximum, um Punkte für die Zählzeiten hinzuzufügen
        add_max_count = K % cycle_count
        add_total_score = 0
        add_score = -float('inf')
        add_count = 0
        add_next_p = P[start_p]
        while True:
            add_total_score += C[add_next_p]
            add_score = max(add_score, add_total_score)
            add_count += 1

            if add_count == add_max_count:
                break
            add_next_p = P[add_next_p]

        if K < cycle_count:
            #Die maximale Anzahl von Versuchen ist der Zyklus_K wenn weniger als zählen% cycle_Schnabel an der besten Stelle zu zählen
            max_score = add_total_score
        else:
            if cycle_total_score >= 0:
                #Wenn ein Zyklus positiv ist, drehen Sie den Zyklus so weit wie möglich und K.% cycle_Schnabel an der besten Stelle zu zählen
                max_score = (K // cycle_count) * cycle_total_score + add_total_score
            else:
                #Wenn ein Zyklus negativ ist, drehen Sie den Zyklus K nicht% cycle_Pause am besten Ort, um zu zählen
                max_score = add_total_score
    # print('max_score', max_score)
    answer = max(answer, max_score)

print(answer)

Ich konnte noch keine Klimaanlage bekommen. Im obigen Code bestehen alle Testeingaben, aber in der Produktion ist die Hälfte WA. Ich denke, die Idee ist richtig, aber ich konnte die Ursache von WA nicht identifizieren ...

Ich weiß nicht, was ich sage, wenn es nur Buchstaben sind, also zeichne ich ein Diagramm. Das Folgende ist eine Illustration des Eingabebeispiels 1.

Anhand der Merkmale dieser Abbildung können wir sehen, dass ein oder mehrere Diagramme mit Zyklen erstellt werden können. Die zu lösende Politik besteht darin, die ganze Straße ehrlich zu versuchen.

1. Entscheiden Sie zuerst, wo Sie anfangen sollen => Versuchen Sie dies auf N Arten
2. Machen Sie von Anfang an eine Runde und notieren Sie die folgenden Ergebnisse 2.1 Gesamtpunktzahl für einen Zyklus 2.2. Punktzahl zum maximalen Zeitpunkt in einem Zyklus 2.3 Anzahl der Bewegungen, die für einen Zyklus erforderlich sind
3. Es ist einfach, wenn K ein ganzzahliges Vielfaches der Anzahl der Bewegungen in einem Zyklus ist, aber es kann Halbwertszeiten geben. In diesem Fall werde ich die Punktzahl unten finden 3.1. Halbzeitnummer 3.2. Maximale Punktzahl auf halber Strecke

Vielleicht sollte dies das Problem lösen, aber es wurde erst am Ende gelöst (Ist es nicht möglich, es damit zu lösen?).

E. Picking Goods

Antwort (normale Version TLE)

R, C, K = map(int, input().split())
scores = [[0] * (C + 1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    scores[r][c] = v
dp = [[[0] *4 for _ in range(C+1)] for _ in range(R+1)]

for i in range(1, R+1):
    for j in range(1, C+1):
        for k in range(4):
            dp[i][j][k] = max(dp[i][j-1][k],
                              dp[i-1][j][3])
        for k in range(3, 0, -1):
            dp[i][j][k] = max(dp[i][j][k],
                              dp[i][j][k-1] + scores[i][j])

answer = dp[R][C][3]
print(answer)

Antwort (Beschleunigung ver AC)

from numba import jit
import numpy as np

@jit
def main():
    R, C, K = map(int, input().split())
    scores = np.zeros((R,C), np.int64)
    for _ in range(K):
        r, c, v = map(int, input().split())
        scores[r-1][c-1] = v
    dp = np.zeros((R+1,C+1,4), np.int64)

    for i in range(1, R+1):
        for j in range(1, C+1):
            for k in range(4):
                dp[i][j][k] = max(dp[i][j-1][k],
                                  dp[i-1][j][3])
            for k in range(3, 0, -1):
                dp[i][j][k] = max(dp[i][j][k],
                                  dp[i][j][k-1] + scores[i-1][j-1])

    return dp[R][C][3]

print(main())

Ich wollte das rechtzeitig lösen. Wenn Sie es normal mit Python erstellen, ist die Zeit nicht rechtzeitig, aber wenn Sie den ursprünglichen Code mit `` numpy``` und `@ jit``` verbessern, vergeht es.

Zuerst las ich das Problem und fand heraus, dass es DP war. Ich kann jedoch immer noch bis zu 2D DP lösen ... Vorerst werde ich den DP schreiben und die Einschränkung von "bis zu 3 in derselben Zeile" ignorieren. Dann wird es wie folgt sein. (Bei der Visualisierung einer zweidimensionalen DP-Tabelle erleichtert die Verwendung von Pandas das Erkennen der vertikalen und horizontalen Richtung, sodass Pandas und Numpy zum Debuggen enthalten sind.)

R, C, K = map(int, input().split())
scores = [[0] * (C + 1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    scores[r][c] = v
dp = [[0] *(C+1) for _ in range(R+1)]

for i in range(1, R+1):
    for j in range(1, C+1):
            dp[i][j] = max(dp[i-1][j] + scores[i][j],
                           dp[i][j-1] + scores[i][j])

print(dp[R][C])

# import numpy as np
# import pandas as pd
# show_dp = np.array(dp)
# show_dp = pd.DataFrame(show_dp)
# print(show_dp)

Bisher ist es einfach. (Während ich das sagte, war es mir vor einer Woche unmöglich, so weit zu kommen, aber hier in der vergangenen Woche >> [Richtlinien zur Verbesserung von Wettkampfprofis und AtCoder, unterrichtet von Red Coder [Zwischenausgabe: Ziel für hellblauen Coder! ]](Https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8% AD% E7% B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% Ich kann das sagen, weil ich das DP-Problem von E5% 8E% BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F gelöst habe. )

Zum Zeitpunkt des Wettbewerbs war es nicht möglich, die Einschränkung "bis zu 3 auf derselben Linie" von hier aus zu übernehmen. Ich wusste, dass ich die Dimension der dp-Tabelle um eins erhöhen und "etwas" tun sollte, aber ich konnte mir dieses "etwas" nicht vorstellen.

Ich werde schreiben "Wenn Sie seitwärts gehen, addieren Sie die Punktzahl bis zum dritten Mal und fügen Sie nichts anderes hinzu", wie es ist. Wenn ich dp löse, muss ich die dp-Tabelle tatsächlich auf Papier schreiben und visualisieren, damit ich kein gutes Bild bekomme, sodass die 3D-dp-Tabelle nicht ganz passt. Ist es ein Ort, an den man sich gewöhnen muss, anstatt zu lernen?

Übrigens, in Python ist es TLE, wenn Sie normal mit dp codieren. Als Richtlinie denke ich, ob ich numpy verwenden soll, um den in der for-Anweisung geschriebenen Teil sofort zu berechnen, pypy zu verwenden oder jit zu verwenden. Es scheint, dass starke Leute natürlich gut mit Numpy rechnen, aber ich kann noch nicht so viel schreiben. In diesem Code hat sogar pypy nicht bestanden, also habe ich es zu einer Funktion gemacht und @jit verwendet.

Dann, wie unten gezeigt, "ist eine kleine Menge an Berechnung viel langsamer und eine große Menge an Berechnung ist viel schneller", und ich habe es geschafft, AC zu bestehen. Ich weiß nicht, warum das passiert, aber wenn Sie mit dp vorerst nicht durchkommen können, versuchen Sie es auf die gleiche Weise.

[Für gewöhnlichen Code]

[Für Code mit @jit]