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. Die zweite Hälfte befasst sich mit dem DE-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 Sie haben das Tutorial des Online-Spiels "AT Chat" beendet und beschlossen, einen bestimmten Ort mit $ N $ Spielern zu besuchen, die dort waren. Diese $ N $ Person ist von $ 1 $ bis $ N $ nummeriert und die Freundlichkeit der Person $ i (1 \ leq i \ leq N) $ ist $ A_i $. Bei einem Besuch kommen $ N $ Personen in beliebiger Reihenfolge an, jeweils $ 1 $. Um nicht verloren zu gehen, haben wir uns für eine Regel entschieden, dass sich bereits angekommene Personen in einem Kreis aufstellen und Neuankömmlinge jede beliebige Position unterbrechen und sich ihr anschließen. Jede andere Person als die erste Person, die ankommt, fühlt sich so wohl wie die geringere Freundlichkeit von "der nächsten Person im Uhrzeigersinn" und "der nächsten Person im Gegenuhrzeigersinn", wenn sie aus der unterbrochenen Position ankommt. Ich fühle es. Der Komfort der ersten Person, die ankommt, beträgt $ 0 $. Was ist der maximale Gesamtkomfort von $ N $ Personen, wenn die Reihenfolge, in der sie ankommen, und die Position der Unterbrechung richtig bestimmt werden?
Um ehrlich zu sein, dachte ich, ich hätte richtig darüber nachdenken sollen. Irgendwie fiel es mir schwer, das Problem zu erkennen, und ich übersprang es, um das E-Problem zu lösen und einen Unterschied zu machen.
abc173d.py
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
ans = 0
for i in range(0, n - 1):
ans += a_list[(i + 1) // 2]
print(ans)
Problemstellung $ N $ ganze Zahlen $ A_1,…, A_N $ sind angegeben. Wenn Sie nur $ K $ -Elemente auswählen, suchen Sie das maximal mögliche Produkt der ausgewählten Elemente. Teilen Sie dann die Antwort durch $ (10 ^ 9 + 7) $ und geben Sie den Rest als Ganzzahl zwischen $ 0 $ und $ 10 ^ 9 + 6 $ aus.
Ich habe über das Problem nachgedacht, indem ich es in positive, negative und 0-Zahlen unterteilt habe, aber aus irgendeinem Grund habe ich verzweifelt die Fälle geschrieben, in denen das Ergebnis von $ K = N $ negativ und wenn es positiv war. Es war Zeit vorbei. Wenn Sie sorgfältig darüber nachdenken, wenn Sie alle verwenden, können Sie es gierig berechnen (Reflexion). Betrachtet man jedoch den zur Studie eingereichten Code, so
4 3
-1 -2 3 4
Ich fragte mich, was mit "AC" los war, das nicht dem Eingabebeispiel wie entsprechen konnte. Menschen, die darüber nachdenken, was in solchen Fällen zu tun ist, haben am Ende keine Zeit mehr, denken nicht zu viel über die Eingabe nach und durchlaufen glücklicherweise die begrenzte Eingabe im Test. Wenn es Leute gibt, die getroffen haben, möchte ich, dass Sie die Rate später anpassen, aber es macht keinen Sinn, zu viel für den kostenlosen Wettbewerb zu verlangen (Schweiß). Derzeit wurde after_contest_01.txt zur Prüfung hinzugefügt, und dieser Code lautet "WA".
abc173e.py
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10**9+7
a_list.sort()
ans = 1
if k % 2 == 1 and a_list[-1] < 0:
for i in range(k):
ans *= a_list[n - 1 - i]
ans %= mod
else:
l = 0
r = -1
mlt1 = a_list[0] * a_list[1]
mlt2 = a_list[-2] * a_list[-1]
count = 0
while True:
if count == k:
break
elif count == k - 1:
ans *= a_list[r] % mod
ans %= mod
break
if mlt1 >= mlt2:
ans *= mlt1 % mod
l += 2
count += 2
if l <= n - 2:
mlt1 = a_list[l + 1] * a_list[l]
else:
ans *= a_list[r] % mod
r -= 1
count += 1
if r >= - n + 1:
mlt2 = a_list[r - 1] * a_list[r]
ans %= mod
print(ans)
Vielen Dank, dass Sie die zweite Hälfte bis zum Ende gelesen haben.
Recommended Posts