Dies ist Qiitas erster Beitrag als Anfänger seit 2 Monaten, seit ich mit dem Programmieren von Wettbewerben (AtCoder) begonnen habe, um Programmieren zu studieren. Dieser Artikel wurde erstellt von @drken Lineare Suche beherrschen! ~ Wenn Sie wissen, was Sie für Aussagen tun können ~, müssen Sie den wunderbaren Artikel verstehen. Außerdem werde ich es als Referenz für ähnliche Personen veröffentlichen, indem ich ein Implementierungsbeispiel in Python veröffentliche. Bitte seien Sie vorsichtig mit Spoilern, da wir einige Beispiele für AtCoder-Probleme veröffentlichen werden. Ich wäre Ihnen sehr dankbar, wenn Sie mir eine Anleitung geben könnten, wenn es unansehnliche Punkte gibt.
ABC 060 B - Choose Integers
Sie wählen einige positive ganze Zahlen und finden deren Summe. Es gibt keine Begrenzung für die Anzahl der Zahlen, die Sie auswählen können, oder für die Anzahl der Ganzzahlen, die Sie auswählen können. Sie können eine beliebig große Ganzzahl oder 5000 Billionen Ganzzahlen auswählen. Alle von Ihnen gewählten Zahlen müssen jedoch ein Vielfaches von A sein. Außerdem muss mindestens eine Ganzzahl ausgewählt werden. Und ich möchte C zur Summe der durch B geteilten Summe machen. Bestimmen Sie, ob Sie eine solche Ganzzahl auswählen können. Wenn möglich JA ausgeben, sonst NEIN.
1≦A≦100 1≦B≦100 0≦C<B
A, B, C = 7,5,1 Antwort: JA Wenn Sie beispielsweise 7,14 auswählen, beträgt die Summe 21, und wenn Sie dies durch 5 teilen, erhalten Sie 1.
Ich denke, es ist ein typisches Beispiel für die Beurteilung durch das Flaggenmanagement. Die Problemstellung besagt "um die Summe der durch B geteilten Summe zu finden", aber da die Summe der Vielfachen von A geteilt wird, dh der Rest wird erhalten, indem das Vielfache von A durch B geteilt wird. Da der maximale Rechenaufwand 100 * 100 beträgt, werden wir daher ehrlich alle durchsuchen.
a, b, c = map(int, input().split())
ans = 'NO' #Halten Sie den Anfangswert des Beurteilungsflags als NEIN
for i in range(101): #Ich möchte den maximalen Eingabewert von 100 mit einem Vielfachen multiplizieren, also 100+1
if a*i % b == c: #Implementieren Sie die Beurteilung der Problemstellung mit if
ans = 'YES' #Wenn das Urteil der if-Anweisung wahr wird, ändern Sie die Antwort in JA
print(ans) #Geben Sie JA aus, wenn das Urteil der if-Anweisung wahr wird
exit() #Da es ausreicht, jemanden auszugeben, hören Sie mit dem Urteil True auf
print(ans) #Wenn das Urteil der if-Anweisung falsch ist, wird NO mit dem Anfangswert ausgegeben.
Legen Sie im vorherigen Code einen Index fest, um den Speicherort zu bestimmen. Dieses Mal besteht der Zweck darin, das Vielfache von Eingang A zu kennen. Das Ergebnis ist # JA 3.
a, b, c = map(int, input().split())
ans = 'NO'
idx = 0 #Der Anfangswert ist 0, um das Vielfache zu kennen
for i in range(101):
if a*i % b == c:
ans = 'YES'
idx = i #Enthält ein Vielfaches, das die Beurteilung der if-Anweisung wahr macht
print(ans, idx) #Wenn das Urteil der if-Anweisung wahr wird, werden YES und ein Vielfaches ausgegeben.
exit()
print(ans, idx) #Wenn die Beurteilung der if-Anweisung False ist, werden NO und 0 mit den Anfangswerten ausgegeben.
Es ist auch möglich, die Position mithilfe von Enumerate zu ermitteln. In diesem Fall müssen wir ein iterierbares Objekt angeben, daher haben wir die Liste im Voraus erstellt. Das Ergebnis ist auch # JA 3.
a, b, c = map(int, input().split())
multiple = [x for x in range(101)]
ans = 'NO'
for idx, i in enumerate(multiple):
if a*i % b == c:
ans = 'YES'
print(ans, idx)
exit()
print(ans, idx)
In Python können Sie eine Liste erstellen und diese mithilfe der Min- und Max-Funktion finden. Wenn die Liste langsam ist, scheint die Verwendung von set sie explosiv zu machen. Der Grund, warum es explosiv wurde, indem es in Python von "in list" zu "in set" wechselte
lst = [i for i in range(-5, 6)]
print(lst) # [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
print(min(lst)) # -5
print(max(lst)) # 5
ABC 081 B - Shift only
An die Tafel sind N positive ganze Zahlen A1,…, A2,…, AN geschrieben. Sunuke kann die folgenden Vorgänge ausführen, wenn alle an die Tafel geschriebenen Ganzzahlen gerade sind.
Bitte fragen Sie, wie oft Sie die Operation maximal ausführen können.
N=3 A=16,12,24 Antwort: 2
Wenn alle Werte in der Liste gerade sind, erhöhen Sie sie um 1. Es ist ein Problem, das leichter zu verstehen ist, wenn es mit while implementiert wird, aber ich wage es, es mit for zu implementieren. Der Maximalwert von A ist 10 ^ 9, aber es muss eine gerade Zahl sein, daher denke ich, dass es ausreichen wird, ihn mit √10 ^ 9 bis zu 31623 Mal zu wiederholen (da es keinen Sinn für Mathematik gibt, ist der Rechenaufwand grob).
n = int(input())
a = list(map(int, input().split()))
cnt = 0 #Flag zum Verwalten des Zählens
for _ in range(31623): # _Bereiten Sie ein leeres Argument für die wiederholte Ausführung mit vor
if all(i % 2 == 0 for i in a): #Übergeben Sie die Liste a an i und beurteilen Sie, ob alles mit allen gleich ist
cnt += 1 #Wenn die Bedingung erfüllt ist, erhöhen Sie cnt um 1
a = [i//2 for i in a] #Teilen Sie jedes Element der Liste a durch 2 und kehren Sie zur Liste a zurück
print(cnt) #Gibt den durch Inkrementieren gezählten numerischen Wert aus
Dies ist ein Implementierungsbeispiel in der while-Anweisung. Das ist einfacher, nicht wahr?
n = int(input())
a = list(map(int, input().split()))
cnt = 0
while all(i % 2 == 0 for i in a):
cnt += 1
a = [i//2 for i in a]
print(cnt)
ABC 051 B - Sum of Three Integers Dies ist ein Beispiel, das in @ darkens Artikel nicht zu finden ist, aber ich denke, es ist eine gute Frage, also schreibe ich es hier. Das Problem besteht darin, die Anzahl der Kombinationen zu ermitteln. Es ist ein Problem, das mit der Essenz gefüllt ist, die notwendig ist, um die Bewegung mehrerer Schleifen von for zu verstehen, unter Berücksichtigung des Rechenaufwands, der Festlegung des Bereichs bedingter Anweisungen und konkurrierender Profis.
Es sind zwei ganze Zahlen K und S gegeben. Es hat drei Variablen X, Y, Z und nimmt einen ganzzahligen Wert an, der 0 ≤ X, Y, Z ≤ K erfüllt. Wie viele Werte können X, Y, Z zugewiesen werden, die X + Y + Z = S erfüllen?
K, S=2, 2 Antwort: 6
Es gibt 6 Sätze von X, Y, Z, die die Bedingung der Problemstellung erfüllen.
X, Y, Z liegen jeweils im Bereich von K. Erstellen Sie daher eine Dreifachschleife von X, Y, Z mit k + 1 (maximal 2500). Wenn die Summe der Kombinationen zu S wird, wird sie um die Anzahl der Male 1 erhöht.
k, s = map(int, input().split())
ans = 0 #Markieren Sie, um die Nummer zu zählen, die die Kriterien erfüllt
for x in range(k+1): #Da der gesamte Bereich von k durchsucht wird, ist der Bereichsbereich von x k+1
for y in range(k+1): #Das gleiche wie oben
for z in range(k+1): #Das gleiche wie oben
if x+y+z == s: #Legen Sie die Bedingung der Problemstellung fest
ans += 1 #Wenn das if-Urteil wahr ist, erhöhen Sie 1
print(ans) #Geben Sie die Nummer aus, die der Bedingung entspricht
Im obigen Beispiel ist die Antwort korrekt, aber je größer der Wert ist, desto länger ist die Ausführungszeit. Ich muss bis zu 2500 ^ 3 = 15625000000 Wege ausprobieren, damit ich es nicht rechtzeitig schaffen kann. Daher ist es notwendig, Wege zu finden, um den Rechenaufwand zu reduzieren.
Wenn es 2500 ^ 2 ist, gibt es 6250000 Wege, also scheint es rechtzeitig zu sein. Reduzieren Sie daher die Anzahl der Schleifen um eins.
Von den Kombinationen von X, Y und Z wird Z der von S subtrahierte Wert sein, sobald X und Y bestimmt sind. Wenn Sie es jedoch gehorsam unter dieser Bedingung implementieren, beträgt die Anzahl der Kombinationen neun.
k, s = map(int, input().split())
ans = 0
for x in range(k+1):
for y in range(k+1):
z = s-x-y
if x+y+z == s:
ans += 1
print(ans)
Dies liegt beispielsweise daran, dass wenn X = 2 und Y = 2 ist, S = 2 ist, es sei denn, Z = –2. Daher muss Z größer oder gleich 0 sein und im Bereich von K liegen. Wenn Sie dies zur bedingten Anweisung hinzufügen, lautet die Antwort 6. Ich konnte die richtige Antwort finden und gleichzeitig die Anzahl der Schleifen um eins reduzieren.
k, s = map(int, input().split())
ans = 0
for x in range(k+1):
for y in range(k+1):
z = s-x-y
if 0 <= z <= k and x+y+z == s:
ans += 1
print(ans)
Wir möchten @drken dafür danken, dass er viele wundervolle Artikel geschrieben hat, unseren Senioren und AtCoder, dass sie einen Ort bieten, an dem sie Spaß am Programmieren haben. Vielen Dank für das Lesen bis zum Ende.
Recommended Posts