AtCoder ABC167 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 167, der am 10.05.2020 (So) in der Reihenfolge von Problem A unter Berücksichtigung der Berücksichtigung stattfand. Das erste Halbjahr befasst sich mit Fragen bis zu ABCD. Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar PDF
Problemstellung Takahashi versucht, sich als Mitglied eines bestimmten Webdienstes zu registrieren. Zuerst habe ich versucht, die ID als $ S $ zu registrieren. Diese ID wurde jedoch bereits von einem anderen Benutzer verwendet. Daher erwog Herr Takahashi, eine Zeichenfolge mit $ 1 $ Zeichen am Ende von $ S $ als ID zu registrieren. Takahashi versucht, eine neue ID als $ T $ zu registrieren. Stellen Sie fest, ob dies die oben genannten Bedingungen erfüllt.
Ich denke, dass dieser Bereich ohne Probleme gelöst werden kann, wenn es sich um Python handelt.
Ich denke, Sie können t [: -1] wie t [: len (t) -1] schreiben.
In beiden Fällen können Sie eine Zeichenfolge ohne das letzte Zeichen der Zeichenfolge erstellen.
--Beispiel: "takaito" → "takait"
abc167a.py
s = input()
t = input()
if s == t[:-1]:
print("Yes")
else:
print("No")
Problemstellung Es gibt $ A $ -Karten mit $ 1 $, $ B $ -Karten mit $ 0 $ und $ C $ -Karten mit $ -1 $. Wenn Sie nur $ K $ von diesen Karten auswählen, was ist der maximal mögliche Wert als Summe der Zahlen, die auf den von Ihnen ausgewählten Karten geschrieben sind?
Um den möglichen Wert zu erhöhen, haben wir eine Karte mit 1 $ so viel wie möglich ausgewählt und es für notwendig gehalten, die Auswahl von -1 $ so weit wie möglich zu vermeiden.
Sie müssen lediglich die bedingte Verzweigung mit der if-Anweisung implementieren.
abc167b.py
a, b, c, k = map(int, input().split())
if a >= k:
print(k)
elif a + b >= k:
print(a)
else:
print(a - (k - (a + b)))
Ich konnte das B-Problem in ungefähr 6 Minuten lösen, also denke ich, dass ich es in meiner idealen Zeit lösen kann.
Problemstellung Takahashi, der mit der wettbewerbsfähigen Programmierung begonnen hat, verfügt über $ M $ Algorithmen, die er lernen möchte. Anfänglich ist das Verständnis jedes Algorithmus $ 0 $. Als Takahashi in die Buchhandlung ging, wurden $ N $ Nachschlagewerke zum Verkauf angeboten. Das $ i $ -te Nachschlagewerk $ (1 \ leq i \ leq N) $ wird für $ C_i $ yen verkauft, und durch Kauf und Lesen jedes $ j (1 \ leq j \ leq M) $ Verbessert das Verständnis des $ j $ -ten Algorithmus um $ A_ {i, j} $. Sie können Ihr Verständnis auch nicht auf andere Weise verbessern. Takahashis Ziel ist es, das Verständnis aller $ M $ -Algorithmen auf $ X $ oder höher zu verbessern. Bestimmen Sie, ob Takahashi das Ziel erreichen kann, und berechnen Sie nach Möglichkeit den Mindestbetrag, der zum Erreichen des Ziels erforderlich ist.
Die Einschränkung ist klein, $ 1 \ leq N, M \ leq 12 $. Es gibt zwei Möglichkeiten, das $ N $ Nachschlagewerk zu kaufen: "Kaufen" oder "Nicht kaufen", und es gibt insgesamt $ 2 ^ N $, sodass Sie es mit einer vollständigen Suche lösen können. Ich dachte, dass ich bei der Suche nach allen häufig rekursive Funktionen verwende. Bei Betrachtung der Übermittlungsergebnisse anderer "AC" gab es überraschenderweise viele Codes, die keine rekursiven Funktionen verwendeten. Ich habe eine rekursive Funktion verwendet, um einen Vektor (z. B. $ [1, 0, 1, 1] $) zu erstellen, der angibt, welches Buch gekauft werden soll, und habe numpy verwendet, um die Matrix zu berechnen. Der Code, den ich eingereicht habe, hat jede Zeile einmal in einer Liste empfangen und in eine Liste mit Beträgen und Verständnis unterteilt, aber auf Twitter "kann ich ihn so erhalten." C, * a = map (int, int, Nur der Teil, der den Wert erhält, wird unter Bezugnahme auf die Beschreibung "input (). Split ())` "geändert.
abc167c.py
import numpy as np
def func(ans, b_list, a_list, c_list, k, x):
if k == 0:
b_list = np.asarray(b_list)
x_list = np.dot(b_list, a_list)
if np.all(x_list >= x):
return np.inner(c_list, b_list)
else:
return ans
ans = min(ans, func(ans, b_list + [1], a_list, c_list, k - 1, x))
ans = min(ans, func(ans, b_list + [0], a_list, c_list, k - 1, x))
return ans
n, m, x = map(int, input().split())
c_list = []
a_list = []
for i in range(0, n):
c, *a = map(int, input().split())
c_list.append(c)
a_list.append(a)
ans = float("inf")
c_list = np.asarray(c_list)
a_list = np.asarray(a_list)
ans = min(ans, func(ans, [1], a_list, c_list, n - 1, x))
ans = min(ans, func(ans, [0], a_list, c_list, n - 1, x))
if ans == float("inf"):
print(-1)
else:
print(ans)
Vor kurzem habe ich das Gefühl, dass es mir schwer fällt, das Problem der vollständigen Suche (Schweiß) zu lösen. Selbst wenn Sie die vollständige Suche verstehen, dauert die Implementierung zu lange, sodass Sie üben müssen, damit Sie intelligent schreiben können.
Problemstellung Es gibt $ N $ Städte im Königreich Takahashi. Die Städte sind von $ 1 $ bis $ N $ nummeriert. Jede Stadt hat $ 1 $ Teleporter. Der Teleporter für die Stadt $ i (1 \ leq i \ leq N) $ wird an die Stadt $ A_i $ weitergeleitet. König Takahashi mag die positive ganze Zahl $ K $. Der egoistische König Takahashi möchte wissen, in welcher Stadt er ankommen wird, wenn er aus einer Stadt mit einem Wert von 1 USD startet und den Teleporter nur K $ mal benutzt. Erstellen Sie hierfür ein Programm für König Takahashi.
Persönlich fand ich es einfacher als das C-Problem. Insbesondere habe ich das starke Gefühl, durch das Beispiel gerettet zu werden (ich habe sofort bemerkt, dass es sich geloopt hat).
Eingabebeispiel 2
6 7272022141732493516 5 2 5 3 2
In Eingabebeispiel 2 ausgehend von der Stadt $ 1 $,
~ Politik ~
Da die Programmierliste (Array) bei 0 beginnt, müssen Sie vorsichtig sein, aber ich dachte, dass die Implementierung nicht so schwierig wäre, wenn Sie vorsichtig wären. Daher wurde zuerst der folgende Code gesendet.
abc167d.py
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
while True:
if next_machi in machi_list:
break
count += 1
machi_list.append(next_machi)
machi = next_machi
next_machi = x[machi] - 1
z = 0
for i in range(0, count):
if machi_list[i] == next_machi:
z = i
break
loop_machi_list = machi_list[z:]
if k < z:
machi = machi_list[k] + 1
print(machi)
else:
k = k - z
machi = loop_machi_list[k % len(loop_machi_list)] + 1
print(machi)
Der obige Code hat jedoch eine langsame Ausführungszeit und ich bekomme "TLE" und Verzweiflung. Ich frage mich, ob der Algorithmus falsch ist. Gibt es eine Möglichkeit, ihn schneller zu machen? Ich war verwirrt. Ich konnte mir jedoch keine bessere Methode vorstellen, daher hatte ich das Gefühl, dass es ein Problem mit der Implementierung gab, und überprüfte es.
Möglicherweise klammerte ich mich an den Strohhalm und bezweifelte, dass die for-Anweisung "if next_machi" in machi_list einen ähnlichen Wert enthielt: "(in der Liste, um zu sehen, ob ich dieselbe Stadt erneut besuchte. Es war der Teil, den ich mache (ich überprüfe). Das war ein schlechter Schachzug. Als das Array groß wurde, dachte ich, es würde einige Zeit dauern, alles zu überprüfen, also bereitete ich sofort ein Diktat vor. Nach dem Umschreiben des Codes wie folgt wurde "AC" sicher übergeben.
abc167d.py
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
machi_dict = {}
while True:
if next_machi in machi_dict:
break
count += 1
machi_dict[next_machi] = 1
machi_list.append(next_machi)
machi = next_machi
next_machi = x[machi] - 1
z = 0
for i in range(0, count):
if machi_list[i] == next_machi:
z = i
break
loop_machi_list = machi_list[z:]
if k < z:
machi = machi_list[k] + 1
print(machi)
else:
k = k - z
machi = loop_machi_list[k % len(loop_machi_list)] + 1
print(machi)
Dieses "TLE" stimmt mit dem Ranking überein, daher wollte ich hier die minimale Implementierungsleistung erlangen, da ich in Zukunft Python bei der Arbeit verwenden werde. Die Algorithmen, die ich im Competition Pro gelernt habe, sind die Jobs, an denen ich in Zukunft beteiligt sein werde, und es scheint ziemlich wahrscheinlich ohne sie, aber es ist sehr lehrreich, schwere Beispiele mit solch detaillierten Implementierungen (Listenbeziehungen usw.) erleben zu können. Insbesondere).
Dies ist das Ende der ersten Hälfte.
Das momentane Ranking, als ich mit der Lösung des D-Problems fertig war, war ziemlich gut, aber danach war es nicht mehr gut, also muss ich etwas mehr lernen. Vielen Dank für das Lesen bis zum Ende der ersten Hälfte.
In der zweiten Hälfte wird das EF-Problem erläutert. Geplant, um in der zweiten Hälfte fortzufahren.
Recommended Posts