AtCoder ABC166 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 166, die am 03.05.2020 (So) aufgetreten sind, beginnend mit Problem A und unter Berücksichtigung der Überlegungen. Die zweite Hälfte befasst sich mit dem DEF-Problem. Klicken Sie hier für die erste Hälfte. 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 Zeigen Sie eine Menge von ganzen Zahlen $ (A, B) $ an, die $ A ^ 5 - B ^ 5 = X $ erfüllen. Für ein gegebenes $ X $ gibt es jedoch eine Garantie dafür, dass es eine Reihe von ganzen Zahlen $ (A, B) $ gibt, die die Bedingung erfüllen. Einschränkungen ・ $ 1 \ leq X \ leq 10 ^ 9 $ ・ $ X $ ist eine ganze Zahl. ・ Es gibt eine Reihe von ganzen Zahlen $ (A, B) $, die die Bedingungen erfüllen.
Nachdem ich das Problem gelesen hatte, dachte ich, dass jedes $ X $ eine Reihe von ganzen Zahlen $ (A, B) $ hat, die die Bedingung erfüllen (zu wenige ...). Selbst wenn ich es in ein Programm eingebe, das verschiedene Muster von $ X $ implementiert, gab es keine Ausgabe, daher dachte ich, dass der Suchbereich nicht ausreicht, und blieb stecken. Nachdem der Wettbewerb beendet war, las ich den Kommentar und dachte, es könnte sein, und als ich das implementierte Programm einreichte, war es "AC", also hätte ich es einreichen sollen ...
abc166d.py
x = int(input())
flag = 0
for a in range(-200, 201):
if flag == 1:
break
for b in range(-200, 201):
if a**5 - b**5 == x:
print(a, b)
flag = 1
break
Problemstellung Als talentierter Agent im Königreich AtCoder haben Sie eine Partei auf dem Handelsplatz infiltriert, um zu verhindern, dass gestohlene streng geheime Informationen in die Hände des Königreichs AlDebaran gelangen. Die Party hat $ N $ Teilnehmer, die jeweils von $ 1 $ bis $ N $ nummeriert sind. Der Teilnehmer $ i $ ist $ A_i $ groß. Durch vorherige Befragung wissen Sie, dass der Handel mit vertraulichen Informationen für Personen im Wert von 2 US-Dollar gilt, die die folgenden Bedingungen erfüllen: ・ Der absolute Wert der Differenz der Zahlen, die von $ 2 $ Personen gehalten werden, entspricht der Summe der Höhen von $ 2 $ Personen. Es gibt $ \ frac {N (N - 1)} {2} $ Möglichkeiten, $ 2 $ Teilnehmer aus $ N $ Teilnehmern auszuwählen und zu koppeln, aber das Paar, das die oben genannten Bedingungen erfüllt, ist Wie viele Möglichkeiten gibt es? Außerdem wissen Sie nicht, was der Inhalt vertraulicher Informationen ist.
Als ich am Wettbewerb teilnahm, war ich mit dem D-Problem festgefahren und konnte das E-Problem nicht lösen, weil ich nicht viel Zeit hatte, aber ich würde gerne in der Lage sein, dieses Problem zu lösen. Ich war mir des "E-Problems F-Problems = schwieriges Problem" bewusst und es ist schwierig, es während des Wettbewerbs zu lösen. Ich habe implementiert, was im Kommentarartikel geschrieben steht, und habe mit dem folgenden Code sicher "AC" erhalten.
abc166e.py
n = int(input())
a_list = list(map(int, input().split()))
l_dict = {}
ans = 0
for i in range(0, n):
a = a_list[i]
ri = i - a
if ri in l_dict:
ans += l_dict[ri]
li = i + a
if li in l_dict:
l_dict[li] += 1
else:
l_dict[li] = 1
print(ans)
Ich war verwirrt über den Ausdruck des absoluten Wertes der Differenz zwischen der Anzahl von $ 2 $ Personen. Wenn Sie sorgfältig darüber nachdenken, können Sie eine Bedingung von $ i <j $ hinzufügen, wenn Sie zwei Personen auswählen. Wenn es negativ ist, scheint es schwierig zu sein, den absoluten Wert zu verarbeiten. Als ich darüber nachdachte, wurde der Verlust bestätigt, also möchte ich nicht denken, dass es schwierig ist.
Problemstellung In einem Spiel gibt es $ 3 $ Variablen, dargestellt durch $ A, B und C $. Im Verlauf des Spiels werden Sie gezwungen sein, $ N $ Entscheidungen zu treffen. Jede Auswahl wird durch die Zeichenfolge $ s_i $ angezeigt. Wenn $ s_i $ "AB" ist, addieren Sie $ 1 $ zu $ A $ oder $ B $ und subtrahieren Sie $ 1 $ vom anderen "AC". Wenn, addieren Sie $ 1 $ entweder zu $ A $ oder $ C $ und subtrahieren Sie $ 1 $ vom anderen, und wenn "BC", addieren Sie $ 1 $ zu $ B $ oder $ C $ und dem anderen Bedeutet, $ 1 $ von zu subtrahieren. Weder $ A, B noch C $ können nach einer Auswahl negativ sein. Bestimmen Sie, ob es möglich ist, alle Auswahlen $ N $ Mal abzuschließen, während diese Bedingung erfüllt ist, und geben Sie in diesem Fall eine solche Auswahlmethode an.
Ich habe den Kommentar gelesen und nur umgesetzt, was geschrieben wurde. Es scheint schwer zu bemerken, dass Sie bei der Verarbeitung nur dann vorsichtig sein müssen, wenn $ A + B + C = 2 $, da es kein Eingabebeispiel gibt. Ich möchte diese Probleme während des Wettbewerbs lösen können.
abc166f.py
def check(s):
if dict_x[s[0]] == 0 and dict_x[s[1]] == 0:
return "NOT"
elif dict_x[s[0]] > 0 and dict_x[s[1]] == 0:
return s[1]
elif dict_x[s[0]] == 0 and dict_x[s[1]] > 0:
return s[0]
elif dict_x[s[0]] == 1 and dict_x[s[1]] == 1:
return "EVEN"
else:
if dict_x[s[0]] > dict_x[s[1]]:
return s[1]
else:
return s[0]
def update(s, mozi):
if s[1] == mozi:
dict_x[s[0]] -= 1
dict_x[s[1]] += 1
else:
dict_x[s[0]] += 1
dict_x[s[1]] -= 1
n, a, b, c = map(int, input().split())
dict_x = {"A": a, "B": b, "C": c}
s_list = []
ans_list = []
flag = 1
for i in range(0, n):
s = input()
s_list.append(s)
if a + b + c == 0:
flag = 0
elif a + b + c == 1:
for s in s_list:
x = check(s)
if x == "NOT":
flag = 0
break
else:
ans_list.append(x)
update(s, x)
elif a + b + c == 2:
i = 0
for s in s_list:
x = check(s)
if x == "NOT":
flag = 0
break
elif x == "EVEN":
if i == len(s_list) - 1:
ans_list.append(s[0])
update(s, x)
elif s == s_list[i + 1]:
ans_list.append(s[0])
update(s, x)
else:
if s[0] in s_list[i + 1]:
ans_list.append(s[0])
update(s, s[0])
else:
ans_list.append(s[1])
update(s, s[1])
else:
ans_list.append(x)
update(s, x)
i += 1
else:
for s in s_list:
x = check(s)
if x == "NOT":
flag = 0
break
elif x == "EVEN":
ans_list.append(s[0])
update(s, s[0])
else:
ans_list.append(x)
update(s, x)
if flag == 1:
print("Yes")
for ans in ans_list:
print(ans)
else:
print("No")
Wenn ich das F-Problem und den Code, den ich selbst geschrieben habe, überprüfe, stelle ich fest, dass immer noch viel Abfall vorhanden ist. Vielen Dank, dass Sie die zweite Hälfte bis zum Ende gelesen haben.
Recommended Posts