Rückblick auf den AtCoder Beginner Contest 165 bis Frage E (Python)
Dies ist ein Übersichtsartikel für Anfänger von Wettkampfprofis.
Die Lösung, die ich hier schreibe, wird geschrieben, während ich mir den Kommentar und die Beiträge anderer Leute ansehe. Es ist möglicherweise nicht das, was Sie tatsächlich eingereicht haben.
Es ist eine Frage zu beantworten, ob K im Bereich von A oder mehr und B oder weniger enthalten ist.
Aus der Einschränkung von $ 1 \ leq A \ leq B \ leq 1000 $, $ 1 \ leq K \ leq 1000 $ ergibt sich kein Problem, wenn Sie einfach nach einem Wert suchen, der die Bedingung im Bereich von $ A $ bis $ B $ erfüllt. ..
N = int(input())
A, B = map(int, input().split())
for i in range(A, B+1):
if i % N == 0:
print('OK')
break
else:
print('NG')
Wenn die eingezahlten 100 Yen einen jährlichen Zinssatz von 1% haben, ist es eine Frage, wie viele Jahre später der angegebene Betrag von X Yen überschritten wird.
Beträge unterhalb des Dezimalpunkts werden abgeschnitten. Beantwortete die Häufigkeit, mit der "while" gedreht wurde, bis der angegebene Betrag überschritten wurde.
X = int(input())
n = 100
count = 0
while n < X:
count += 1
n = int(n * 1.01)
print(count)
Für die Eingabe von $ a, b, c, d $ erhalten Sie $ d $ Punkte, wenn $ A_b --A_a = c $. Wenn Sie eine Folge von Zahlen $ \ boldsymbol {A} $ erstellen können, müssen Sie die maximale Gesamtpunktzahl beantworten.
Es sieht nach einem verwirrenden Problem aus ... aber die Länge der Sequenz $ N $, das Maximum $ M $, ist $ 1 \ leq N \ leq 10, 1 \ leq M \ leq 10 $, wenn $ a, b gegeben ist Die Anzahl von, c, d $ $ Q $ wird auch als $ 1 \ leq Q \ leq 50 $ angegeben. Ich dachte, das wäre ein Kreisverkehr.
Ich habe "itertools.combinations_with_replacement ()" für Round-Robin verwendet. Beachten Sie, dass die Zahlenspalte $ A $ einen festen sortierten Wert hat, jedoch doppelte Werte möglich sind.
import itertools
N, M, Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]
Max = 0
for C in itertools.combinations_with_replacement(range(1, M + 1), N):
score = sum([d for a, b, c, d in abcd if C[b-1] - C[a-1] == c])
Max = max(Max, score)
print(Max)
Nachtrag
Ist das wirklich eine Nummer, die gedrückt werden kann? $ O (M ^ N Q) $, richtig? Ich war besorgt und versuchte zu rechnen.
import itertools
print(len(list(itertools.combinations_with_replacement(range(1, 11), 10))))
# 92378
Es scheint, dass Sie gehen können. Mit Blick auf den Kommentar war diese vollständige Suche für mich allein schwierig. Es lebe Python. Es lebe die Bibliothek.
Ist das Problem, $ x $ zu finden, was der Maximalwert ist.
Abgesehen vom mathematischen Beweis fragte ich mich, ob ich den Maximalwert von $ x $ so finden sollte, dass $ floor (x / B) = 0 $ ist. Die Bedingung wird von dem größten $ B-1 $ unter $ N $ erfüllt, dh dem kleineren von $ B-1 $ oder $ N $.
Deshalb habe ich folgendes geschrieben.
A, B, N = map(int, input().split())
x = min(B-1, N)
print(A*x // B - A * (x//B))
Mathematische Erklärung
Ich habe die mathematische Erklärung nicht verstanden, deshalb werde ich die Erklärung lesen.
Und sag es. Wenn der Wert von $ x $ in dieser Formel um $ B $ erhöht wird, wird der erste Term auf der rechten Seite immer um $ A $ erhöht. Der zweite Term wird immer um $ A $ reduziert. Dies wird abgebrochen und die Summe ändert sich nicht. Mit anderen Worten gilt die folgende Formel.
Sie müssen also nicht über den Bereich von $ B \ leq x $ nachdenken. Finden Sie den Maximalwert im Bereich von $ 0 \ leq x <B $, $ 0 \ leq x \ leq N $.
In diesem Bereich ist der Wert des zweiten Terms, der ursprünglich negativ ist, immer 0, daher sollte der Wert des ersten Terms, der eine monotone Zunahme darstellt, innerhalb des Bereichs maximiert werden. Das heißt, maximieren Sie $ x $ innerhalb des Bereichs.
Ich verwende den zweiten Begriff nicht, daher können Sie ihn wie folgt schreiben.
A, B, N = map(int, input().split())
print(A * min(B-1, N) // B)
Es ist ein Problem, darüber nachzudenken, wie man eine Kombination nimmt, bei der sich die Gegner nicht überschneiden, wenn $ N $ Teilnehmer gleichzeitig 1vs1 Stein-Papier-Schere für $ M $ Spiele und $ N $ Zeiten spielen.
Die Problemstellung ist äußerst kompliziert. Was fragst du?
Angenommen, $ N = 9 $ Personen haben an diesem Turnier teilgenommen. Es wird 9 Sätze von Übereinstimmungen geben. Von hier aus setzen wir $ M = 3 $ und machen drei Paare.
Wählen Sie ein Paar von 1 oder 2, wie Sie möchten.
Selbst wenn Sie in diesem Zustand 9 Mal drehen, werden keine Gegner dupliziert.
Als nächstes nehmen wir 3, 5 Paare.
Dies führt nicht zu Duplikaten.
Als nächstes nehmen wir ein Paar 6 und 7.
Dies führt zu Duplikaten. Ein Paar von 1 und 2 Schichten und ein Paar von 6 und 7 Schichten nehmen das gleiche auf dem Weg.
Wie kann ich das beheben? Es wurde um eins oder zwei verschoben, also verschieben wir es diesmal um drei.
Diesmal gibt es keine Vervielfältigung. Das Problem ist, ein solches Paar zu machen.
Mit anderen Worten kann dieses Problem wie folgt umformuliert werden.
"$ M $ Paare von ($ A_i, B_i $) mit $ B_i - A_i = 1, 2, 3, ..., M $ ausgeben, ohne dass Werte dupliziert werden."
Sie haben keine anständige Suche durchgeführt, um dies zu lösen. (TLE ist herausgekommen.) Die Form wird von Anfang an festgelegt und platziert.
Deshalb habe ich es wie folgt implementiert.
N, M = map(int, input().split())
halfPos = -(-N//2)
qPos = halfPos // 2
q3Pos = qPos + halfPos
for m in range(1, M+1):
if m % 2:
print(qPos-m//2, qPos+m//2+1)
else:
print(q3Pos-m//2, q3Pos+m//2)
Dieser Artikel endet hier. Dies ist das erste Mal, dass ich es in der Produktion mit ABCDE gelöst habe.
Recommended Posts