[PYTHON] AtCoder Beginner Contest 119 Rückblick auf frühere Fragen
Benötigte Zeit
Impressionen
Obwohl es mühsam war, das C-Problem zu lösen, konnte ich es mit einer einfachen Lösung lösen, so dass ich die mangelnde Konzentration im Bachacon spürte. Außerdem zeige ich die Formel an, die von $ umgeben ist, aber aus irgendeinem Grund wird ein Zeilenumbruch eingefügt. Ich wäre Ihnen dankbar, wenn Sie mir sagen könnten, wie ich damit umgehen soll. → In Bezug auf dieses Problem scheint es, dass bei Verwendung der Unterleiste (_) ein Problem auftreten kann. (29.04.2020)
Problem A
Ich wusste nicht, ob es 2019 war ..., falsch verstanden ... Wenn Sie split verwenden, können Sie mit einem Schrägstrich teilen.
answerA.py
s=list(map(int,input().split("/")))
if s[0]<2019:
print("Heisei")
elif s[0]>2020:
print("TBD")
else:
print("TBD" if s[1]>4 else "Heisei")
answerA_better.py
s=list(map(int,input().split("/")))
print("TBD" if s[1]>4 else "Heisei")
B-Problem
Alle Beträge sollten berücksichtigt werden, je nachdem, ob es sich um Bitmünzen handelt oder nicht.
answerB.py
n=int(input())
cnt=0.0
for i in range(n):
x,u=input().split()
x=float(x)
cnt+=(x if u=="JPY" else x*380000.0)
print(cnt)
C-Problem
Es war schwieriger als D (weiße Augen). ** Es ist klar, dass Sie alle Straßen ausprobieren können **, aber es war mühsam, alle Straßen aufzuschreiben. Als ich darüber nachdachte, wie ich es entwerfen sollte, verging die Zeit enorm. Beachten Sie beim Ausprobieren zunächst, dass ** MP nur davon abhängt, wie Bambus ausgewählt wird, und nicht in dieser Reihenfolge **. Auf dieser Grundlage sollten Sie überlegen, ** welchen Bambus von A, B, C Sie verwenden möchten ** (A, B, C, nicht verwendet). Antwort wurde auf diese Weise implementiert.) Nummerieren Sie zunächst die ursprünglichen n Bambusse (entsprechend A bis C) 0 bis 2, um zu prüfen, welcher Bambus verwendet werden soll: A, B oder C (1). Zu diesem Zeitpunkt wurden die Bambusse festgelegt, die zur Herstellung von A-, B- und C-Bambus verwendet werden können (oder nicht). Außerdem muss zu diesem Zeitpunkt mindestens eine Zahl von 0 bis 2 angezeigt werden. Wenn also keine Zahl vorhanden ist, wechselt der Prozess zur nächsten Schleife (2). Auf dieser Grundlage werden wir überlegen, aus welchem Bambus jeweils A, B, C hergestellt werden soll. ** Wählen Sie jedoch eine beliebige Anzahl von Bambussen aus, aus denen jeweils A, B, C hergestellt werden kann. Da es gut ist, betrachten Sie eine Teilmenge ** durch Bitfolge (3). Wenn Sie sich jedoch auch in diesem Fall nicht für Bambus entscheiden, werden wir dies nicht berücksichtigen, sodass wir solche Fälle ausschließen (4). Wenn man auf diese Weise denkt, kann der MP, der erforderlich ist, um die Längen von A, B und C in jedem Fall zu bestimmen, eindeutig bestimmt werden (5), also unter Berücksichtigung des Mindestwerts für jeden Gegenstand Sie können den minimalen MP finden. Ich habe das Obige implementiert und es wurde wie folgt, aber ** Ich war verwirrt, weil ich zu schlecht darin war, Variablen zu benennen ** und ich konnte ** die obige Diskussion in meinem Kopf organisieren ** Es hat lange gedauert, es zu lösen. Ich denke, ich sollte es aufschreiben, um meine Gedanken wie jedes Mal organisiert zu halten, aber wenn ich es löse, vergesse ich es. Ich dachte, ich hätte keine andere Wahl, als die Einstellung zu prägen, wenn ich sie wiederholt löse.
answerC.py
import itertools
n,*abc=map(int,input().split())
l=[int(input()) for i in range(n)]
inf=100000000000000
mi=inf
for i in list(itertools.product([i for i in range(3)],repeat=n)):#(1)↓
sub=[[] for j in range(3)]
for j in range(n):
sub[i[j]].append(j)
mi_sub=0
for j in range(3):
l_sub=len(sub[j])
if l_sub==0:#(2)
mi_sub=inf
break
mi_subsub=inf
for k in range(2**l_sub):#(3)↓
mi_subsubsub=[0,0]
for l_subsub in range(l_sub):#(5)↓
if ((k>>l_subsub) &1):
mi_subsubsub[0]+=1
mi_subsubsub[1]+=l[sub[j][l_subsub]]
if mi_subsubsub[0]!=0:#(4)
mi_subsub=min(mi_subsub,abs(mi_subsubsub[1]-abc[j])+mi_subsubsub[0]*10-10)
mi_sub+=mi_subsub
mi=min(mi,mi_sub)
print(mi)
itertools.product Eine Funktion, die ein direktes Produkt aus mehreren Listen generieren kann (Sie können einen Iterator mit mehreren Schleifen präzise schreiben). Durch Angabe mehrerer Listen im Argument wird ein Objekt vom Typ itertools.product generiert und als Rückgabewert zurückgegeben. Durch Drehen der for-Anweisung können dann alle Kombinationen einzeln abgerufen werden (es ist auch möglich, sie aufzulisten). Darüber hinaus ist es auch möglich, ein direktes Produkt derselben Liste zu erzeugen, indem die Anzahl der Wiederholungen in Wiederholung angegeben wird, und in diesem Problem wird das direkte Produkt mit Wiederholung = n für die Liste m erzeugt.
D Problem
Zuerst dachte ich, dass es eine Abschnittsplanung und eine Imosu-Methode gibt, aber ich dachte ruhig und es war nicht so. Wenn Sie das Problem eher anhand des Problems als anhand des Algorithmus betrachten, werden Sie nicht vom Sumpf abhängig und können mehr nachdenken. Überlegen Sie nun, wann Sie an einem bestimmten x waren. Dann wird x von $ s_ {i-1} $, $ s_i $ und $ t_ {j-1} $, $ t_j $ ($ s_0 $, $ t_0 $) umgeben sein. , $ s_ {a-1} $, $ t_ {b-1} $ ist etwas anders, wenn es draußen ist). Zu diesem Zeitpunkt besteht die minimale Bewegung darin, sich zu bewegen, um entweder einen Punkt von $ s_ {i-1} $ oder $ s_i $ oder einen Punkt von $ t_ {j-1} $ oder $ t_j $ zu durchlaufen. Es ist klar, dass die Entfernung erreicht werden kann (** Zeichnen Sie ein Diagramm, bevor Sie dies bemerken **), sodass Sie alle vier Möglichkeiten von $ 2 \ times2 $ (und $ s_0 $, $ t_0 $,) betrachten können. Wenn es außerhalb von $ s_ {a-1} $, $ t_ {b-1} $ liegt, müssen weniger Kandidatenpunkte übergeben werden.). Darüber hinaus kann der Bereich von x durch den Umfang der logarithmischen Berechnung unter Verwendung der Dichotomie bestimmt werden, so dass das Programm ausreichend schnell ist. Diese werden wie folgt implementiert: Außerdem ist die Reisedistanz kürzer, wenn Sie vom nächstgelegenen der beiden ausgewählten Punkte aus besuchen.
answerD.py
a,b,q=map(int,input().split())
s=[int(input()) for i in range(a)]
t=[int(input()) for i in range(b)]
x=[int(input()) for i in range(q)]
from bisect import bisect_left
for i in range(q):
y=bisect_left(s,x[i])
z=bisect_left(t,x[i])
k=([0] if y==0 else [a-1] if y==a else [y-1,y])
l=([0] if z==0 else [b-1] if z==b else [z-1,z])
mi=100000000000000
for n in k:
for m in l:
if abs(s[n]-x[i])>abs(t[m]-x[i]):
sub1,sub2=t[m],s[n]
else:
sub1,sub2=s[n],t[m]
mi=min(mi,abs(sub1-x[i])+abs(sub2-sub1))
print(mi)
Korrektur (2020/05/03)
Ein Linkfehler wurde behoben.
Recommended Posts