[PYTHON] AtCoderBeginnerContest173 Review & Summary (Erste Hälfte)

AtCoder ABC173 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 173, der am 05.07.2020 (So) in der Reihenfolge von Problem A unter Berücksichtigung der Berücksichtigung stattfand. Das erste Halbjahr befasst sich mit Fragen bis ABC. Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar PDF

Problem A Zahlung

Problemstellung Kaufen Sie $ N $ Yen-Artikel im Geschäft. Wie viel kostet es, sich zu ändern, wenn Sie nur mit 1000-Dollar-Yen-Scheinen bezahlen? Die Zahlung erfolgt jedoch mit der erforderlichen Mindestanzahl von 1000-Dollar-Yen-Scheinen.

Ich dachte, ich könnte die Änderung anhand der letzten drei Ziffern des $ N $ Yen berechnen, also berechnete ich den Rest, indem ich $ N $ durch $ 1000 $ dividierte. Sie können die gewünschte Ausgabe erhalten, indem Sie den Rest von $ 1000 $ subtrahieren. Im Fall von $ 1000 x x $ Yen beträgt die Änderung ursprünglich $ 0 $ Yen, der Rest jedoch $ 0 $, sodass die Ausgabe "1000" wird. Weil es endet, habe ich eine bedingte Verzweigung mit der if-Anweisung erstellt. Bei der Lösung der Überlegung dachte ich, dass die Berechnungsmethode ohne bedingte Verzweigung geschrieben wurde.

abc173a.py

n = int(input())
k = n % 1000
if k == 0:
    print(0)
else:
    print(1000 - k)

Problem B Zusammenfassung des Richterstatus

Problemstellung Herr Takahashi nahm am Programmierwettbewerb AXC002 teil und übermittelte den Code an Frage A. Es gibt $ N $ Testfälle für dieses Problem. Für jeden Testfall $ i (1 \ leq i \ leq N) $ wird die Zeichenfolge $ S_i $ angegeben, die das Richterergebnis darstellt, sodass das Richterergebnis "AC", "WA", "TLE", "RE" ist. Bitte finden Sie die Anzahl derer, die waren. Informationen zum Ausgabeformat finden Sie in der Ausgabespalte.

Ich habe den Input ehrlich in das Diktat eingebracht.

abc173b.py

n = int(input())
key_dict = {"AC": 0, "WA": 0, "TLE": 0, "RE": 0}
for i in range(n):
    key = input()
    key_dict[key] += 1
print("AC x " + str(key_dict["AC"]))
print("WA x " + str(key_dict["WA"]))
print("TLE x " + str(key_dict["TLE"]))
print("RE x " + str(key_dict["RE"]))

Ich möchte in der Lage sein, wie der Python-Code des offiziellen Kommentars zu schreiben.

abc173b.py

N = int(input())
s = [input() for i in range(N)]
for v in ['AC', 'WA', 'TLE', 'RE']:
    print('{0} x {1}'.format(v, s.count(v)))

C Problem H und V.

Problemstellung In der Zeile $ H $ und in der Spalte $ W $ befindet sich eine Zelle, die aus Zellen besteht. Die Farbe der Zelle der Zeile $ i $ von oben und der Spalte $ j $ von links $ (1 \ leq i \ leq H, 1 \ leq j \ leq W) $ wird als Zeichen $ c_ {i, j} $ angegeben Wenn $ c_ {i, j} $ "." Ist, ist es weiß, und wenn es "#" ist, ist es schwarz. Gehen Sie wie folgt vor: ・ Wählen Sie einige Zeilen (möglicherweise $ 0 $ Zeile) und einige Spalten (möglicherweise $ 0 $ Spalte) aus. Malen Sie dann alle Zellen in der ausgewählten Zeile und die Zellen in der ausgewählten Spalte in Rot. Angesichts der positiven ganzen Zahl $ K $. Wie viele Zeilen und Spalten können ausgewählt werden, so dass nach der Operation nur noch $ K $ schwarze Zellen übrig bleiben? Hier werden die beiden Auswahlmöglichkeiten als unterschiedlich angesehen, wenn Zeilen oder Spalten nur in einer ausgewählt werden.

Ich dachte, ich müsste eine vollständige Suche durchführen, also löste ich sie mit einer rekursiven Funktion, aber die Implementierung dauerte lange.

abc173c.py

import numpy as np
def funk(matrix, n, k, no_list, h, w):
    if n == 0:
        mask = np.ones((h, w))
        for i in range(h):
            if no_list[i] == 1:
                mask[i,] = 0
        for j in range(w):
            if no_list[h+j] == 1:
                mask[:,j] = 0
        if np.sum(matrix * mask) == k:
            return 1
        else:
            return 0
    ans = 0
    ans += funk(matrix, n - 1, k, no_list + [1], h, w)
    ans += funk(matrix, n - 1, k, no_list + [0], h, w)
    return ans

ans = 0
h, w, k = map(int, input().split())
n = h + w
matrix = np.zeros((h, w))
for i in range(h):
    line = input()
    for j in range(w):
        if line[j] == "#":
            matrix[i,j] = 1
        else:
            matrix[i,j] = 0
no_list = []
ans += funk(matrix, n, k, no_list, h, w)
print(ans)

Dies ist das Ende der ersten Hälfte. Vor kurzem wurde der offizielle Kommentar sehr sorgfältig beschrieben, daher hoffe ich, dass Sie sich für die detaillierte Lösung darauf beziehen können. Vielen Dank für das Lesen bis zum Ende der ersten Hälfte.

In der zweiten Hälfte wird das DEF-Problem erläutert. Fortsetzung in der zweiten Hälfte.