AtCoder ABC170 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 170, der am 14.06.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 $ 5 $ Es gibt zwei Variablen $ x_1, x_2, x_3, x_4, x_5 $. Der Variablen $ x_i $ wurde zunächst die Ganzzahl $ i $ zugewiesen. Sunuke-kun hat aus diesen Variablen $ 1 $ ausgewählt und dieser Variablen $ 0 $ zugewiesen. Sie erhalten den Wert von $ 5 $ Variablen, nachdem Sunuke-kun dies getan hat. Bitte antworten Sie, welcher Variablen Sunuke-kun $ 0 $ zugewiesen hat.
Zur Übermittlung wurde die for-Anweisung so gedreht, dass der Teil mit 0 Elementen ausgegeben wurde. Die meisten Programmiersprachen beginnen mit $ 0 $ im Array. Wenn Sie also darauf achten, sollten Sie sich keine Sorgen um WA machen müssen.
abc170a.py
x = list(map(int, input().split()))
for i in range(5):
if x[i] == 0:
print(i + 1)
Nachdem ich mir die Erklärung nach dem Abschluss angesehen hatte, dachte ich, dass die Antwort $ 15 - x_1 - x_2 - x_3 - x_4 - x_5 $ sein würde.
Problemstellung Es gibt einige Tiere im Garten. Dies sind entweder Kräne mit $ 2 $ Beinen oder Schildkröten mit $ 4 $ Beinen. Takahashi sagt: "Die Gesamtzahl der Tiere im Garten beträgt $ X $, und die Gesamtzahl ihrer Beine beträgt $ Y $." Stellen Sie fest, ob es eine Kombination aus Kran- und Schildkrötennummern gibt, die diese Aussage korrekt macht.
Ich habe die Regeln mit if-Anweisungen in der Reihenfolge hinzugefügt, in der ich dachte.
abc170b.py
x, y = map(int, input().split())
if y < 2 * x or x * 4 < y:
print("No")
else:
if y % 2 == 1:
print("No")
else:
print("Yes")
Problemstellung Gegeben die ganze Zahl $ X $ und die ganze Zahl $ p_1,…, p_N $ der Länge $ N $. Finden Sie die Ganzzahl (nicht unbedingt positiv), die nicht in der Ganzzahlfolge $ p_1,…, p_N $ enthalten ist, die $ X $ am nächsten kommt, dh diejenige mit der geringsten absoluten Differenz zu $ X $. .. Wenn es mehrere solcher Ganzzahlen gibt, beantworten Sie bitte die kleinste.
Die Zahlen, die nicht in der Ganzzahlzeichenfolge enthalten sind, wurden in der Reihenfolge der Eingabe $ X $ gesucht. Wenn $ N $ groß ist, braucht es viel Zeit für `wenn x in Liste:`, also ändere ich die Liste in diktieren, aber dieses Mal, weil $ N $ klein ist, habe ich es so belassen, wie es ist.
Wenn die Eingabe beispielsweise $ 6 $ ist, wird die Suche in der Reihenfolge 6, 5, 7, 4, 8, ... ausgeführt. (Das Programm hat die Eingabe $ x = 6 ± 0 $ zweimal überprüft, aber ich dachte, dass es keinen großen Unterschied in der Ausführungszeit geben würde, also habe ich sie in einer Form implementiert, die einfach zu implementieren ist.)
abc170c.py
x, n = map(int, input().split())
p_list = list(map(int, input().split()))
for i in range(0, n // 2 + 2):
if x - i not in p_list:
print(x - i)
break
if x + i not in p_list:
print(x + i)
break
Problemstellung Bei einer Folge von $ N $ in der Länge $ A $. Bitte beantworten Sie die Anzahl der Ganzzahlen $ i (1 \ leq i \ leq N) $, die die folgenden Eigenschaften erfüllen. ・ Für jede ganze Zahl $ j (1 \ leq j \ leq N) $, die $ i \ neq j $ ist, ist $ A_i $ nicht durch $ A_j $ teilbar
Ich habe während des Wettbewerbs über verschiedene Ideen nachgedacht, konnte sie aber nicht lösen. Ich habe den folgenden Code für "TLE" eingereicht.
abc170dTLE.py
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
flag_list = [1] * len(sorted_dict)
i = 0
for key, count in sorted_dict:
if flag_list[i] == 0:
i += 1
continue
if count > 1:
flag_list[i] = 0
i += 1
j = i
for key1, count1 in sorted_dict[i:]:
if flag_list[j] == 0:
j += 1
continue
if key1 % key == 0:
flag_list[j] = 0
j += 1
print(sum(flag_list))
Ich dachte, dass der Rechenaufwand in der zweiten Hälfte reduziert werden könnte, indem sortiert und geprüft wird, ob die kleineren die größeren brechen können, aber das war nicht gut.
Tatsächlich wird es verwaltet, indem es in einen Satz gestellt wird und $ 2 $ mal, $ 3 $ mal, $ 4 $ mal, ..., $ k $ mal ($ k $ ist $ a_i × k \ leq a_ {max) Es scheint, dass es gelöst werden kann, indem die maximale Ganzzahl $ k $), die} $ erfüllt, aus der Menge entfernt wird. Ich konnte nicht daran denken.
abc170d.py
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
a_set = set(a_list)
m = max(a_list)
for key, count in sorted_dict:
if key in a_set:
j = key * 2
while j <= m:
a_set.discard(j)
j += key
if count > 1:
a_set.discard(key)
print(len(a_set))
Dies ist das Ende der ersten Hälfte. Persönlich habe ich in letzter Zeit die Zinsen gesenkt, aber das ist natürlich, weil ich mir keine Zeit für die Lösung früherer Fragen in Datenanalyse-Wettbewerben oder beim Schreiben von Papieren sichern konnte. Ich habe viel zu lernen für den Wettbewerb, deshalb möchte ich es nach und nach verdauen (ich möchte die Mindestmethode bis zum nächsten Wettbewerb verstehen und implementieren). Zumindest vorerst möchte ich, dass ABC die Gewohnheit beibehält, jedes Mal für eine Weile teilzunehmen. Vielen Dank für das Lesen bis zum Ende der ersten Hälfte.
Die zweite Hälfte wird das EF-Problem erklären, aber ich glaube nicht, dass ich rechtzeitig einen Artikel schreiben kann (Schweiß).
Recommended Posts