Codeforces Round # 609 (Div.2) Critique Bacha (10/8)

Les résultats de cette fois

Impressions de cette époque

C'était tôt jusqu'au problème C, mais à partir de là ... Je dois dire que je devrais faire de mon mieux parce que le problème D était trop long et que j'étais découragé de le lire, mais c'est tout à fait un reflet que je n'ai pas pu passer le problème E après une heure et demie. J'ai noté les points de réflexion du problème E, donc je ferai attention après cela.

Problème A

Puisque $ d $ est couvert, considérez ce qui est préférable d'allouer **. À ce stade, s'il s'agit de $ e > f $, il est préférable de le trier dans le premier type, et s'il s'agit de $ e \ <f $, il est préférable de le trier dans le second type. Lorsque $ e = f $, peu importe celui que vous utilisez.

Par conséquent, si vous considérez les cas par $ e > f $, $ e \ <f $, ce sera comme suit.

(1) Dans le cas de $ e > f $ Il est préférable de choisir le premier type, seulement $ m = min (a, d) $. De plus, comme le reste de $ d $ est $ d-m $, seul $ min (b, c, d-m) $ peut être sélectionné pour le deuxième type.

(2) Dans le cas de $ e \ <f $ Il est préférable de choisir le premier type, seulement $ m = min (b, c, d) $. De plus, comme le reste de $ d $ est $ d-m $, seul $ min (a, d-m) $ peut être sélectionné pour le deuxième type.

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)

Problème B

(Ci-après, le noir est B et le blanc est W.)

Vous pouvez le faire jusqu'à 3 $ n $, alors pensez à le construire de manière pratique. Aussi, nous allons opérer pour que toutes les couleurs soient les mêmes, mais nous envisagerons de s'unifier à ** B . Aussi, si vous effectuez l'opération pour inverser le $ i, i + 1 $ th uniquement lorsque le $ i $ th est W dans l'ordre du plus petit $ i $, ** Toujours garder le B avant le $ i $ th Tu peux faire. A la fin de cette opération, il y a deux façons: $ BB… BB, BB… BBW $. Dans le premier cas, les couleurs sont déjà unifiées, de sorte que les opérations jusqu'à ce point sont sorties. Dans ce dernier cas, lorsque B est pair, vous pouvez créer le W entier en sélectionnant B de manière appropriée. De plus, dans ce dernier cas, si B est impair, c'est impossible (parce que $ \ parce que $ B et W ont une quantité de changement pair).

En outre, ce qui précède est au plus 2n $ fois, donc la condition est remplie.

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])))

Problème C

Vous pouvez atteindre $ (s \ _x, s \ _y) $ via l'un des quatre points ci-dessus, et ** lorsque vous passez un point, les autres points ne passent pas **, donc ces quatre points Vous pouvez mettre une tente dans l'un d'eux.

Considérant que vous pouvez l'atteindre dans la plus courte distance

(1) Les coordonnées de la maison passant par les coordonnées A → $ y $ sont $ s \ _y + 1 $ ou plus (2) Les coordonnées de la maison passant par B → les coordonnées $ x $ sont $ s \ _x + 1 $ ou plus (3) Les coordonnées de la maison passant par les coordonnées C → $ y $ sont inférieures à $ s \ _y-1 $ (4) Les coordonnées de la maison passant par D → les coordonnées $ x $ sont inférieures à $ s \ _x-1 $

Puisqu'il suffit de satisfaire, trouvez la valeur maximale lorsque chacun est compté.

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)

Problème D

Le problème était difficile à lire. Je vais sauter cette fois.

E problème

Il y a trois problèmes principaux à considérer dans ce numéro:

(1) ** L'expérience est appropriée ** → Au lieu de "Je veux trouver ** 〇〇 propriétés **, je vais faire △△", mais "Je ne sais pas, donc je vais faire △△ pour le moment". (2) ** Il convient de couper la police ** → ** Je ne peux pas dire si c'est différent ** logiquement ** (3) ** Le mémo est sale ** → ** Le sens de la considération est différent **

J'écrirai un commentaire en vérifiant ce qui précède.

Il est difficile de compter si chaque nombre de chemins contient $ z $, alors ** considérez ce que le nombre de chemins contient $ z $ **.

Par exemple, ** expérimentez ** avec $ z = 1 $, et ce sera comme suit. … (3)

Vous pouvez voir que les nombres sortent dans un motif radial, mais vous ne pouvez pas saisir la règle même si vous ne considérez que le cas de ** $ z = 1 $ **, alors considérez le cas de $ z = 4 $ et $ z = 4 Considérez les nombres qui ont des chemins contenant $ dans l'ordre croissant. … (1) Ensuite, vous pouvez voir que des nombres tels que 4 ~ 5 → 8 ~ 11 → 16 ~ 23 →… incluent $ z $ dans le chemin. En généralisant cela, nous pouvons voir que les nombres contenus dans $ [z, z + 1], [2z, 2z + 3], [4z, 4z + 7]… $ ont des chemins contenant $ z $ ( ✳︎). De plus, si $ z $ est pair, ce sera comme ci-dessus, mais s'il est impair, doublez-le pour le rendre pair, puis comptez-le **.

Par conséquent, même si vous comptez combien de $ z $ sont inclus dans le chemin jusqu'à $ n $, le nombre d'intervalles est d'environ un multiple constant de $ \ log {n} $, donc le nombre incluant $ z $ dans le chemin est $ O. Vous pouvez compter par (\ log {n}) $. De plus, $ [z, z + 1], [2z, 2z + 3], [4z, 4z + 7]… $ car plus le $ z $ est petit, plus le nombre de nombres contiendra $ z $ dans le chemin * * A la monotonie **. De plus, comme la méthode de comptage est différente pour les paires et les impairs, ** il est nécessaire d'effectuer une dichotomie pour chacun des paires et des impairs **.

D'après ce qui précède, si la fonction de comptage du nombre incluant $ z $ dans le chemin est $ calc (z) $ (le retour est une valeur booléenne de $ k $ ou plus même si compté), $ calc (z) $ est Puisqu'il est vrai quand $ z $ est petit et faux quand il est grand, le maximum $ z $ qui est vrai est calculé par dichotomie. C'est un peu gênant de diviser les cas par hasard, mais ce n'est pas difficile à implémenter si vous vous référez à cet article. ** Il suffit de faire attention à la définition des valeurs limites $ l, r $ **. Notez également que l'article précédent recherche la valeur minimale et cette fois-ci la valeur maximale, il est donc nécessaire de remplacer tous les rôles de $ l et r $.

(✳︎)… Je vais omettre la preuve, mais quand $ z $ est pair, il est clair que le nombre d'intervalles $ [z, z + 1] $ peut être exprimé, alors trouvez le nombre récursivement à partir d'ici. Tu peux le voir.

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))

Problème F

Je vais sauter cette fois