[PYTHON] AtCoder Beginner Contest 119 Rückblick auf frühere Fragen

Benötigte Zeit

スクリーンショット 2020-01-26 16.03.45.png

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

AtCoder Beginner Contest 072 Rückblick auf frühere Fragen
AtCoder Beginner Contest 085 Rückblick auf frühere Fragen
AtCoder Beginner Contest 062 Rückblick auf frühere Fragen
AtCoder Beginner Contest 113 Rückblick auf frühere Fragen
AtCoder Beginner Contest 074 Rückblick auf frühere Fragen
AtCoder Beginner Contest 127 Rückblick auf frühere Fragen
AtCoder Beginner Contest 119 Rückblick auf frühere Fragen
AtCoder Beginner Contest 151 Rückblick auf frühere Fragen
AtCoder Beginner Contest 075 Rückblick auf frühere Fragen
AtCoder Beginner Contest 054 Rückblick auf frühere Fragen
AtCoder Beginner Contest 110 Rückblick auf frühere Fragen
AtCoder Beginner Contest 117 Rückblick auf frühere Fragen
AtCoder Beginner Contest 070 Rückblick auf frühere Fragen
AtCoder Beginner Contest 105 Rückblick auf frühere Fragen
AtCoder Beginner Contest 112 Rückblick auf frühere Fragen
AtCoder Beginner Contest 076 Rückblick auf frühere Fragen
AtCoder Beginner Contest 089 Rückblick auf frühere Fragen
AtCoder Beginner Contest 069 Rückblick auf frühere Fragen
AtCoder Beginner Contest 079 Rückblick auf frühere Fragen
AtCoder Beginner Contest 056 Rückblick auf frühere Fragen
AtCoder Beginner Contest 087 Rückblick auf frühere Fragen
AtCoder Beginner Contest 067 Rückblick auf frühere Fragen
AtCoder Beginner Contest 093 Rückblick auf frühere Fragen
AtCoder Beginner Contest 046 Rückblick auf frühere Fragen
AtCoder Beginner Contest 123 Überprüfung früherer Fragen
AtCoder Beginner Contest 049 Rückblick auf frühere Fragen
AtCoder Beginner Contest 078 Rückblick auf frühere Fragen
AtCoder Beginner Contest 081 Rückblick auf frühere Fragen
AtCoder Beginner Contest 047 Rückblick auf frühere Fragen
AtCoder Beginner Contest 060 Rückblick auf frühere Fragen
AtCoder Beginner Contest 104 Rückblick auf frühere Fragen
AtCoder Beginner Contest 057 Rückblick auf frühere Fragen
AtCoder Beginner Contest 121 Rückblick auf frühere Fragen
AtCoder Beginner Contest 126 Rückblick auf frühere Fragen
AtCoder Beginner Contest 090 Rückblick auf frühere Fragen
AtCoder Beginner Contest 103 Rückblick auf frühere Fragen
AtCoder Beginner Contest 061 Rückblick auf frühere Fragen
AtCoder Beginner Contest 059 Rückblick auf frühere Fragen
AtCoder Beginner Contest 044 Rückblick auf frühere Fragen
AtCoder Beginner Contest 083 Rückblick auf frühere Fragen
AtCoder Beginner Contest 048 Rückblick auf frühere Fragen
AtCoder Beginner Contest 124 Rückblick auf frühere Fragen
AtCoder Beginner Contest 116 Rückblick auf frühere Fragen
AtCoder Beginner Contest 097 Rückblick auf frühere Fragen
AtCoder Beginner Contest 088 Rückblick auf frühere Fragen
AtCoder Beginner Contest 092 Rückblick auf frühere Fragen
AtCoder Beginner Contest 099 Rückblick auf frühere Fragen
AtCoder Beginner Contest 065 Rückblick auf frühere Fragen
AtCoder Beginner Contest 053 Rückblick auf frühere Fragen
AtCoder Beginner Contest 094 Rückblick auf frühere Fragen
AtCoder Beginner Contest 063 Rückblick auf frühere Fragen
AtCoder Beginner Contest 107 Rückblick auf frühere Fragen
AtCoder Beginner Contest 071 Rückblick auf frühere Fragen
AtCoder Beginner Contest 064 Rückblick auf frühere Fragen
AtCoder Beginner Contest 082 Rückblick auf frühere Fragen
AtCoder Beginner Contest 084 Rückblick auf frühere Fragen
AtCoder Beginner Contest 068 Rückblick auf frühere Fragen
AtCoder Beginner Contest 043 Rückblick auf frühere Fragen
AtCoder Beginner Contest 098 Rückblick auf frühere Fragen
AtCoder Beginner Contest 114 Rückblick auf frühere Fragen