[PYTHON] Codeforces Runde # 609 (Div. 2) Bacha Review (10/8)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Es war früh bis zum C-Problem, aber von dort ... Ich muss sagen, dass ich mein Bestes geben sollte, weil das D-Problem zu lang war und ich davon abgehalten wurde, es zu lesen, aber es ist eine ziemliche Überlegung, dass ich das E-Problem nach anderthalb Stunden nicht bestehen konnte. Ich habe die Reflexionspunkte im E-Problem aufgeschrieben, daher werde ich von nun an vorsichtig sein.

Problem A

Da $ d $ abgedeckt ist, überlegen Sie, welches am besten zuzuweisen ist **. Wenn es zu diesem Zeitpunkt $ e > f $ ist, ist es am besten, es in den ersten Typ zu sortieren, und wenn es $ e \ <f $ ist, ist es am besten, es in den zweiten Typ zu sortieren. Wenn $ e = f $, spielt es keine Rolle, welches Sie verwenden.

Wenn Sie also die Fälle mit $ e > f $, $ e \ <f $ betrachten, ist dies wie folgt.

(1) Im Fall von $ e > f $ Am besten wählen Sie den ersten Typ, nur $ m = min (a, d) $. Da der Rest von $ d $ $ d-m $ ist, kann nur $ min (b, c, d-m) $ für den zweiten Typ ausgewählt werden.

(2) Im Fall von $ e \ <f $ Am besten wählen Sie den ersten Typ, nur $ m = min (b, c, d) $. Da der Rest von $ d $ $ d-m $ ist, kann nur $ min (a, d-m) $ für den zweiten Typ ausgewählt werden.

A.py

a,b,c,d,e,f=[int(input()) for i in range(6)]
if e<f:
    m=min(b,c,d)
    ans=m*f
    b-=m
    c-=m
    d-=m
    ans+=min(a,d)*e
else:
    m=min(a,d)
    ans=m*e
    a-=m
    d-=m
    ans+=min(b,c,d)*f
print(ans)

B-Problem

(Im Folgenden ist Schwarz B und Weiß W.)

Sie können es bis zu $ 3n $ tun, also ziehen Sie es in Betracht, es bequem zu bauen. Wir werden auch so arbeiten, dass alle Farben gleich sind, aber wir werden in Betracht ziehen, ** B ** zu vereinheitlichen. Wenn Sie die Operation zum Invertieren von $ i, i + 1 $ th nur ausführen, wenn das $ i $ th W in der Reihenfolge des kleinsten $ i $ ist, ** behalten Sie das B immer vor dem $ i $ th Du kannst tun**. Am Ende dieser Operation gibt es zwei Möglichkeiten: $ BB… BB, BB… BBW $. Im ersteren Fall sind die Farben bereits vereinheitlicht, sodass die Operationen bis zu diesem Punkt ausgegeben werden. Im letzteren Fall, wenn B gerade ist, können Sie das gesamte W erstellen, indem Sie B entsprechend auswählen. Auch im letzteren Fall ist es unmöglich, wenn B eine ungerade Zahl ist (weil sowohl $ , weil $ B als auch W eine gerade Änderungsmenge haben).

Außerdem beträgt der oben genannte Wert höchstens $ 2n $, sodass die Bedingung erfüllt ist.

B.py

n=int(input())
s=list(input())
ans=[]
if s[0]=="W":
    ans.append(0)
    s[0]="B"
    if s[1]=="W":
        s[1]="B"
    else:
        s[1]="W"
for i in range(1,n-1):
    if s[i]=="W":
        s[i]="B"
        if s[i+1]=="W":
            s[i+1]="B"
        else:
            s[i+1]="W"
        ans.append(i)
if s!=["B" for i in range(n)] and n%2==0:
    print(-1)
    exit()
if s!=["B" for i in range(n)]:
    for i in range(n-1):
        if i%2==0:
            ans.append(i)

print(len(ans))
print(" ".join(map(str,[i+1 for i in ans])))

C-Problem

Sie können $ (s \ _x, s \ _y) $ über einen der oben genannten vier Punkte erreichen, und ** wenn Sie einen Punkt passieren, passieren die anderen Punkte nicht **, also diese vier Punkte Sie können ein Zelt in eines von ihnen stellen.

Bedenkt man, dass man es in kürzester Entfernung erreichen kann

(1) Koordinaten des Hauses, die durch A → $ y $ -Koordinaten verlaufen, sind $ s \ _y + 1 $ oder mehr (2) Koordinaten des Hauses, die durch B → $ x $ -Koordinaten verlaufen, sind $ s \ _x + 1 $ oder mehr (3) Die Koordinaten des Hauses, die durch C → $ y $ -Koordinaten verlaufen, sind kleiner als $ s \ _y-1 $ (4) Die Koordinaten des Hauses, die durch D → $ x $ -Koordinaten verlaufen, sind kleiner als $ s \ _x-1 $

Da es ausreicht, um zu erfüllen, finden Sie den Maximalwert, wenn jeder gezählt wird.

C.py

import sys
input=sys.stdin.readline
n,sx,sy=map(int,input().split())
a,b,c,d=0,0,0,0
for i in range(n):
    x,y=map(int,input().split())
    if x<=sx-1:
        a+=1
    elif x>=sx+1:
        b+=1
    if y<=sy-1:
        c+=1
    elif y>=sy+1:
        d+=1
m=max(a,b,c,d)
print(m)
if a==m:
    print(sx-1,sy)
elif b==m:
    print(sx+1,sy)
elif c==m:
    print(sx,sy-1)
else:
    print(sx,sy+1)

D Problem

Das Problem war schwer zu lesen. Ich werde diesmal überspringen.

E Problem

In dieser Ausgabe sind drei Hauptprobleme zu berücksichtigen:

(1) ** Experiment ist angemessen ** → Anstelle von "Ich möchte ** 〇〇 Eigenschaften ** finden, werde ich △△ tun", sondern "Ich weiß es nicht, also werde ich △△ vorerst tun". (2) ** Es ist angebracht, die Police abzuschneiden ** → ** Ich kann nicht sagen, ob es anders ist ** logisch ** (3) ** Memo ist schmutzig ** → ** Die Betrachtungsrichtung ist unterschiedlich **

Ich werde einen Kommentar schreiben, während ich das oben Gesagte überprüfe.

Es ist schwierig zu zählen, ob jede Anzahl von Pfaden $ z $ enthält. ** Überlegen Sie also, wie viele Pfade $ z $ enthalten **.

Zum Beispiel ** experimentiere ** mit $ z = 1 $ und es wird wie folgt sein. … (3)

Sie können sehen, dass die Zahlen in einem radialen Muster ausgegeben werden, aber Sie können die Regel nicht verstehen, selbst wenn Sie nur den Fall von ** $ z = 1 $ ** betrachten. Betrachten Sie also den Fall von $ z = 4 $ und $ z = 4 Betrachten Sie die Zahlen mit Pfaden, die $ in aufsteigender Reihenfolge enthalten. … (1) Dann können Sie sehen, dass Zahlen wie 4 ~ 5 → 8 ~ 11 → 16 ~ 23 →… $ z $ in den Pfad aufnehmen. Wenn wir dies verallgemeinern, können wir sehen, dass die in $ [z, z + 1], [2z, 2z + 3], [4z, 4z + 7]… $ enthaltenen Zahlen Pfade haben, die $ z $ enthalten ( ✳︎). Wenn $ z $ gerade ist, ist es wie oben, aber wenn es ungerade ist, verdoppeln Sie es, um es gerade zu machen, und zählen Sie es dann **.

Selbst wenn Sie zählen, wie viele $ z $ bis zu $ n $ im Pfad enthalten sind, beträgt die Anzahl der Intervalle ungefähr ein konstantes Vielfaches von $ \ log {n} $, sodass die Anzahl, die $ z $ im Pfad enthält, $ O ist. Sie können mit (\ log {n}) $ zählen. Außerdem $ [z, z + 1], [2z, 2z + 3], [4z, 4z + 7]… $, denn je kleiner $ z $ ist, desto mehr Zahlen enthalten $ z $ im Pfad * * Hat Monotonie **. Da die Zählmethode für gerade und ungerade unterschiedlich ist **, ist es auch erforderlich, eine Dichotomie für jede gerade und ungerade ** durchzuführen.

Wenn die Funktion zum Zählen der Zahl einschließlich $ z $ im Pfad $ calc (z) $ ist (Rückgabe ist ein Bool-Wert von $ k $ oder mehr, selbst wenn gezählt), ist $ calc (z) $ Da es wahr ist, wenn $ z $ klein ist, und falsch, wenn es groß ist, wird das Maximum $ z $, das wahr ist, durch Dichotomie berechnet. Es ist etwas mühsam, die Fälle nach dem Zufallsprinzip aufzuteilen, aber es ist nicht schwierig, sie zu implementieren, wenn Sie auf [diesen Artikel] verweisen (https://qiita.com/DaikiSuyama/items/84df26daad11cf7da453). ** Sie müssen nur bei der Definition der Grenzwerte $ l, r $ ** vorsichtig sein. Beachten Sie außerdem, dass im vorherigen Artikel nach dem Minimalwert und diesmal nach dem Maximalwert gesucht wird. Daher müssen alle Rollen von $ l und r $ ersetzt werden.

(✳︎)… Ich werde den Beweis weglassen, aber wenn $ z $ gerade ist, ist es klar, dass die Anzahl der Abschnitte $ [z, z + 1] $ ausgedrückt werden kann, also finden Sie die Zahl rekursiv von hier aus. Du kannst es sehen.

E.py

n,k=map(int,input().split())
def calc(z):
    global n
    if z>n:
        return False
    if z==0:
        return True
    if z%2==1:
        ans=1
        now=2*z
        co=1
        if k==1:
            return True
        elif now>n:
            return False
    else:
        ans=0
        now=z
        co=1
    #print(ans,now,co)
    while True:
        #print(n,now+2*co-1,now)
        #print(n-(now)+1)
        if n<=now+2*co-1:
            ans+=max(0,n-(now)+1)
            #print(ans)
            break
        else:
            now*=2
            co*=2
            ans+=(co)
            #print(ans)
    #print(ans)
    return ans>=k
realans=[]
#odd(2x-1)
l=1
r=n//2+2
while l+1<r:
    y=l+(r-l)//2
    if calc(2*y-1):
        l=y
    else:
        r=y
realans.append(2*l-1)
#even(2x)
l=0
r=n//2+2
while l+1<r:
    y=l+(r-l)//2
    if calc(2*y):
        l=y
    else:
        r=y
realans.append(2*l)
print(max(realans))

F Problem

Ich werde diesmal überspringen