[PYTHON] AtCoder Beginner Contest 165 Bewertung
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Das C-Problem schien schwerwiegend zu sein und es war nicht so schwierig, also hätte ich es richtig in Betracht ziehen sollen. Ich habe versucht, ein E-Problem zu erstellen, aber ich konnte nicht genug darüber nachdenken und es während des Wettbewerbs nicht fertig lösen. Ich bin sehr enttäuscht.
Problem A
Als ich dachte, ich hätte die Richtlinie geändert, weil der for-Satz in Problem A auftauchte, fehlte mir einfach meine eigene Überlegung. Alles, was Sie tun müssen, ist sicherzustellen, dass a bis b Vielfache von k sind, damit der Code folgendermaßen aussieht: Es ist auch einfacher, mit einer beliebigen Funktion zu schreiben.
A.py
k=int(input())
a,b=map(int,input().split())
for i in range(a,b+1):
if i%k==0:
print("OK")
break
else:
print("NG")
B-Problem
Wiederholen Sie den Vorgang des Multiplizierens mit 1,01 und des Abwertens, bis X Yen oder mehr erreicht sind, und zählen Sie die Summe der Vorgänge.
B.py
import math
ans=0
x=int(input())
y=100
while y<x:
ans+=1
y=math.floor(1.01*y)
print(ans)
C-Problem
Diesmal wird es ein grobes C-Problem sein.
Ist es in dem Moment, in dem Sie es sehen, ein gewichteter Union Find? Diese Überlegung basiert jedoch auf ** Algorithmen ** und sollte daher niemals durchgeführt werden. In dieser Ausgabe konnte ich die Grundlagen bekräftigen (ich möchte schlampig sein ...).
Auf den ersten Blick erfordert dieses Problem auch eine vollständige Suche in $ M ^ {10} $ Straßen, aber die Einschränkung von $ 1 \ leqq A_1 \ leqq A_2 \ leqq… \ leqq A_N \ leqq M $ kann ziemlich eng sein. Offensichtlich (Sie können es durch Experimentieren mit kleinen N, M erkennen. ** Ich habe dieses Experiment während des Wettbewerbs vernachlässigt. **) ist $ A_1, A_2,…, A_N $ weniger als $ M ^ {10} $ Straßen Das können Sie vermuten. Daher werde ich vorerst versuchen, es mit der Politik der vollständigen Suche zu lösen. Sie können herausfinden, wie viele Möglichkeiten es gibt, indem Sie sich Erklärung ansehen, aber ich denke, es ist ein wenig schwierig, dies während des Wettbewerbs zu berücksichtigen.
Hier **, wenn Sie die Richtlinie für die vollständige Suche auswählen können **, ist der Rest nicht so schwierig. Da Sie $ A_1, A_2,…, A_N $ in der Reihenfolge von vorne festlegen können, können Sie hier DFS verwenden (Sie können N für Anweisungen verschachteln, aber ** viele Fors wie diese. Wenn Sie wahrscheinlich eine verschachtelte Anweisung haben **, können Sie leicht ** einen ähnlichen Prozess in DFS schreiben **).
Bereiten Sie im Fall von DFS ein Array (oder eine Zeichenfolge ←, die später beschrieben wird) mit bis zu $ A_1, A_2,…, A_d $ und einer Funktion vor, die die obigen drei Argumente d und $ A_d $ verwendet, und d kommt zu N. Wenn ja, wird die Punktzahl der Zahlenfolge berechnet, und wenn N nicht erreicht wird, kann der Wert über $ A_d $ und unter M der nächste $ A_ {d + 1} $ sein, sodass alle von ihnen rekursive Funktionen sind. Rufen Sie einfach den Fall an. Zu diesem Zeitpunkt ist es möglicherweise einfacher zu verstehen, wenn Sie bis zu $ A_1, A_2,…, A_d $ als Zeichenfolge speichern. Mit anderen Worten, das gleiche Ergebnis kann erhalten werden, indem $ 1 \ leqq A_1 \ leqq A_2 \ leqq… \ leqq A_N \ leqq M \ leqq 10 $ in $ 0 \ leqq A_1 \ leqq A_2 \ leqq… \ leqq A_N \ leqq M-1 \ leqq 9 $ geändert wird. Daher kann jede Zahl durch eine Ziffer vereinheitlicht werden, und der Code zum Zeitpunkt der Wiederholung wird leichter sichtbar, wenn er als Zeichenfolge betrachtet wird.
Nach dem Wettbewerb fand ich es heraus, indem ich mir maspys Tweet ansah, aber in der iterierbaren Python-Datenstruktur x Es scheint, dass es eine Funktion ** Kombinationen mit Ersetzung gibt, die das Duplizieren von Elementen ermöglicht und eine Teilzeichenfolge von Elementen der Länge r zurückgibt (erstes Argument ist x und zweites Argument ist r). Darüber hinaus werden die Kombinationen in lexikalischer Reihenfolge generiert. Wenn also die ursprüngliche iterierbare Datenstruktur sortiert wird, können die Kombinationen als sortierte Taples erhalten werden. Wenn Sie in diesem Problem `range (1, m + 1)` für x und `` `n``` für r angeben, ist das Tupel, das mit dem DFS-generierten Array (oder String) übereinstimmt Kann generiert werden. Ich möchte die Funktionen rund um itertools einmal überprüfen.
C.py
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
ans=0
R=[range(i,m) for i in range(m)]
def dfs(s,d,l):
global n,m,Q,ans
if d==n:
ans_=0
for k in Q:
a,b,c,e=k
if int(s[b-1])-int(s[a-1])==c:
ans_+=e
ans=max(ans,ans_)
else:
for i in R[l]:
dfs(s+str(i),d+1,i)
dfs("",0,0)
print(ans)
C.py
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
ans=0
for s in combinations_with_replacement(range(1,m+1),n):
ans_=0
for k in Q:
a,b,c,d=k
if s[b-1]-s[a-1]==c:
ans_+=d
ans=max(ans_,ans)
print(ans)
D Problem
Persönlich war es einfach, aber viele Leute schienen es schwierig zu finden. Immerhin ist ** die erste Richtlinie wichtig **, deshalb möchte ich mein Verständnis verbessern.
Erstens, wenn man den Fall betrachtet, in dem x ein Vielfaches von B ist, wird es 0, und ich dachte, wenn der Rest von ** B klein ist, wird das Berechnungsergebnis klein sein **. Wenn darunter $ x = k \ mal B + l \ (0 \ leqq l \ leqq B-1)
Auch die Annahme von $ 0 \ leqq l \ leqq B-1 $ und $ [\ frac {Al} {B}] $ steigt monoton in Bezug auf $ l $ (im weiteren Sinne), so dass $ l = B-1 $ das Maximum ist. Wird sein. Im Fall von $ n \ leqq B-1 $ ist n das Maximum, daher lautet die gewünschte Antwort $ [\ frac {A \ times min (B-1, n)} {B}] $.
answerD.py
a,b,n=map(int,input().split())
print(a*min(b-1,n)//b)
Ich habe ein bisschen Code Golf gespielt. Es war ein kürzester.
answerD_shortest.py
a,b,n=map(int,input().split());print(a*min(b-1,n)//b)
E Problem
Nachdem ich während des Wettbewerbs über das C-Problem nachgedacht hatte, ** machte ich es mit einer geeigneten Richtlinie **, sodass ich den Fall nicht gut aufteilen konnte, wenn n gerade war. Ich habe yumas Tweet auf Twitter gefunden und konnte nach meiner eigenen Methode AC betreiben, also habe ich angefangen, einen Kommentar zu schreiben, aber <Schriftfarbe = "rot"> Ich konnte das Muster nicht einmal mit n erklären. </ font> Ich denke, ich werde die Fortsetzung der Erklärung bald schreiben, aber bitte verzeihen Sie mir. Darüber hinaus werden die im offiziellen Kommentar aufgeführten kurz erläutert.
Bei solchen Konstruktionsproblemen sollten Sie ** zuerst Ihre Hand bewegen ** (Experiment), um die Zuordnung von Zahlen zum Schlachtfeld zu finden. Als Ergebnis des Experiments dachte ich dann, dass die folgenden Kombinationen zweckmäßig wären und dass jede Kombination von M und N existieren könnte.
Diese Kombination sieht auf den ersten Blick gut aus. Da sich die Teilnehmer mit der Nummer 1 zu Beginn an die Stelle der Nummer M bewegen (** Sie werden in dieser Zeit nicht denselben Teilnehmer treffen ) und wenn die Anzahl auf NM steigt, gehen Sie in umgekehrter Reihenfolge zurück () ** Sie werden in dieser Zeit nicht denselben Teilnehmer treffen **) Das ist in Ordnung. Nachdem ich es eingereicht hatte, wurden alle Testfälle in der zweiten Hälfte zu WA.
Persönlich habe ich das Gefühl, dass die Politik von hier falsch war. ** Wenn Sie den Fall klären, in dem die vorherige Kombination nicht gilt **, ** können Sie ** die obige Kombination so ändern, dass sie weiterhin gilt **. Betrachten wir nun den Fall, in dem die obige Kombination nicht gilt. Dann können die folgenden Überlegungen angestellt werden.
Erstens, wenn die Person mit der Nummer 1 A und die Person mit der Nummer N-M B ist, Wenn M gerade ist, kämpfen Sie gegen B, wenn A zur Nummer M wird (in der Abbildung rot dargestellt). Kämpfen Sie also nicht gegen B, wenn A die Nummer N-M oder höher ist. Wenn B die Nummer M ist, ist A die Nummer N, und wenn A die Nummer N-M ist, ist B die Nummer 2N-M. Wenn A die Zahl N-M oder später wird, kämpft es daher nicht gegen B, wenn A ungerade ist und ** N ungerade ist **. Im Gegenteil, wenn M ungerade ist, kämpft es nicht gegen B, bis A zur Nummer M wird, also muss es gegen B kämpfen, wenn A zur Nummer N-M oder später wird. Wenn A die Nummer NM ist, ist B die Nummer 2N-M, und wenn A die Nummer NM oder höher ist, kämpft B, wenn A gerade ist, ** N ist ungerade *. Es wird *.
Daher kann für jede Person dasselbe getan werden (∵ ** Verwenden Sie nur Gewinnchancen und Gewinnchancen, um das Kampfmuster zu bestimmen oder nicht **). Wenn also N ungerade ist, kann jede Person dieselbe Kombination wie zuvor ausführen. Es kann gesagt werden, dass Sie nicht gegen denselben Teilnehmer spielen werden. Daher möchte ich die Zeit berücksichtigen, in der das verbleibende N gerade ist, aber von hier aus ist es das Dämonentor.
Zu viel Dämonentor! </ Font>
→ Es tut mir leid, aber die Erklärung von hier reicht mir nicht aus. Es wäre sehr dankbar, wenn Sie es mit Kommentaren ergänzen oder Anfragen bearbeiten könnten.
Von hier aus habe ich versucht, die in Offizielle Erklärung beschriebene Methode zu erklären, aber ich habe keine Zeit, sie zu schreiben, also eine leichte Erklärung. Ich werde es mit beenden.
Wie Sie aus den beiden obigen Mustern sehen können (die Abbildung in Offizielle Erklärung), ** der Abstand der Zahlenkombination ** (In der ersten Abbildung sind 1 und 5 Abstände von 4, 2 und 4 sind 2 usw.) Sie können sehen, dass sie alle unterschiedlich sind. Daher können Sie n Zahlen anordnen und so nehmen, dass sie alle unterschiedliche Abstände haben ** ($ \ daher $ Wenn dieser Abstand unterschiedlich ist, wird derselbe Teilnehmer nicht mehrmals spielen). Wie in der obigen Abbildung gezeigt, können Sie, wenn Sie es in der Mitte teilen und so abrufen, dass der Abstand auf der linken Seite gerade und auf der rechten Seite ungerade ist, eine Reihe von Zahlen mit unterschiedlichen Abständen ohne Verschwendung abrufen. Beachten Sie auch, dass der maximale Abstand $ [\ frac {n} {2}] $ beträgt ($ , da $ Maximum größer als $ [\ frac {n} {2}] $ ist Der Satz von Zahlen entspricht nicht dem Motiv, da einige mit der gleichen Entfernung herauskommen können.
… Das ist eine leichte Erklärung. Für weitere Informationen fragen Sie bitte in den Kommentaren.
✳︎ Es dauerte einige Stunden, um sowohl Python als auch PyPys kürzeste und schnellste zu erfassen (Stand: 3. Mai 2020). Insbesondere denke ich, dass die kürzeste Person exzellenten Code auf ihre eigene Weise angewendet hat. Ich spiele damit herum, daher werde ich den Code nicht erklären, aber ich glaube, ich konnte Bitoperationen effektiv einsetzen.
answerE_bymyself.py
#Richtlinienkodex, den ich während des Wettbewerbs erstellt habe
n,m=map(int,input().split())
if n%2==1:
for i in range(m):
print(i+1,n-i)
else:
for i in range(m):
if i<m/2:
print(i+1,n-i)
else:
print(i+1,n-i-1)
answerE_editorial.py
n,m=map(int,input().split())
if n%2==1:
l=n//2
for i in range(m):
if i%2==1:
print(i//2+1,l-i//2)
else:
print(l+i//2+1,n-i//2)
else:
l=n//2
for i in range(m):
if i%2==0:
print(i//2+1,l-i//2)
else:
print(l+i//2+2,n-i//2)
answerE_shortest.py
n,m=map(int,input().split())
for i in range(m):print(i+1,n-i-((i>=m/2)&~n))
answerE_fastest.py
def main():
n,m=map(int,input().split())
if n%2==1:
x=[f"{i+1} {n-i}" for i in range(m)]
print(" ".join(x))
else:
x=[f"{i+1} {n-i}" if i<m/2 else f"{i+1} {n-i-1}" for i in range(m)]
print(" ".join(x))
if __name__ == "__main__":
main()
F Problem
Ich habe zu viel Zeit mit anderen Themen verbracht und es gibt heute einen Wettbewerb, daher werde ich ihn nicht einmal wiederholen. Ich werde es zu einem anderen Zeitpunkt überprüfen.
Recommended Posts