AtCoder Grand Contest 041 Critique

Je voudrais passer en revue le AGC041 que j'ai eu l'autre jour.

Les résultats de cette fois

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

Je pense que je peux améliorer mon score car j'ai pu le compléter pour la première fois, mais comme je n'avais qu'à changer un peu d'avis sur le problème C, j'ai voulu le terminer trois fois.

Problème A

J'ai trouvé une solution assez rapidement, mais j'ai craché 2WA parce que j'ai rapidement soumis une solution qui était clairement erronée et j'ai soumis du code Python en tant que code C ++. Premièrement, la chose la plus simple à comprendre est lorsque la distance entre la table A et la table B est égale. Dans ce cas, les joueurs de tennis de table à chaque table doivent réduire la distance entre les tables de 2 et afficher la distance divisée par 2. Ensuite, nous devons considérer le cas où la distance entre la table A et la table B est impaire. Dans ce cas, vous pouvez faire la distance entre les deux tables même en allant à la fin (table 1 ou table N) et y rester en un tour. À ce stade, il est nécessaire de considérer celui le plus proche de la fin, il suffit donc de sortir le côté min avec à la fois c et d dans le code suivant. (Si vous codez la formule ici correctement, elle devient WA.) La clé de ce problème est ** de classer l'état pendant la transition **. Dans ce problème, vous pouvez voir que si vous gagnez à la table 1 et si vous perdez à la table N, vous ne pouvez que ** ** ne pas passer à une autre table. Il est également facile de considérer que les cas où les deux sont proches l'un de l'autre sont clairement minimisés, auquel cas la distance est égale, et lorsqu'ils sont au bord, la planéité change.

answerA.py


x=[]
n,a,b=map(int,input().split())
if (b-a)%2==0:
    print((b-a)//2)
else:
    c=(a-1)+(b-a+1)//2
    d=(n-b)+(b-a+1)//2
    print(min(c,d))

Problème B

Pour le moment, organisez les personnes par ordre décroissant. À ce stade, les questions A1 à Ap peuvent être adoptées sans condition parce que la question P est adoptée dans le concours. Ici, si vous pouvez changer la question de Ap, qui a le score le plus bas parmi les questions P, et sélectionner une question plus petite que cela, la question peut être adoptée dans le concours. Si v <= p, continuez à voter pour A1 ~ Ap-1 et Aj (j> = p + 1), et sachez que Aj devrait pouvoir dépasser Ap. En revanche, dans le cas de v> p, il y a encore plus de votes pour Aj (j> = p + 1) même si tous les juges votent pour A1 ~ Ap-1, Aj et ** Aj dépasse Ap. Vous pouvez voir qu'il n'est pas possible de juger simplement en faisant ** (car s'il y a un vote dans Ap, il peut dépasser Aj). Maintenant, en considérant comment choisir les voix restantes pour le juge, nous devons également remarquer que même si nous votons pour Ak (k> j + 1), nous dépasserons Aj. En d'autres termes, même si vous votez pour A1 ~ Ap-1 et Aj ~ An (à ce stade, le score de la question votée est + m) et mettez les votes restants du juge dans Ap ~ Aj-1, Aj va On peut dire que Aj peut être adopté dans le concours s'il est Al (p <= l <= j-1) ou plus pour tout l. Vous pouvez également voir que Ap ~ Aj-1 est égal à Aj lorsque les votes restants du juge sont ** votés au maximum afin que Ap ne dépasse pas Aj (à ce moment, Ap ~ Aj-1 est l'original Comme il est plus grand que Aj, il est garanti que le nombre maximum de voix pour chacun ne dépassera pas m.) De plus, ils sont classés par ordre décroissant et ** vous ne pourrez pas participer au concours après un certain Aj, vous pouvez donc rechercher un tel Aj par dichotomie **. Pour expliquer l'intérieur de la fonction d'adoption, tout d'abord, A1 à Ap-1 n'ont pas besoin d'être considérés en premier lieu, ils sont donc découpés en [p-1:]. b est la valeur lorsque l'on vote au maximum pour Ax + p + 1 (x est considéré comme un indice 0), si b n'est pas supérieur à Ap, il ne peut pas être adopté, donc False est retourné (1), al est pour tous les juges Dans le nombre total de votes (cependant, A1 ~ Ap-1, Ax + p + 1 ~ An votera, donc j'ai déjà soustrait ce montant), si al est égal ou inférieur à 0, tous les votes des juges sont épuisés Par conséquent, True est renvoyé (2), s est le nombre de votes requis pour obtenir Ap ~ Ax + p Ax + p + 1 (b). Si al dépasse s, False, sinon True. Rendre.

answerB.py


n,m,v,p=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort(reverse=True)
a=a[p-1:]
le=len(a)
l,r=0,le-1

def adopt(x):
    global a,n,m,v,p
    b=a[x]+m
    #(1)
    if b<a[0]:
        return False
    al=v*m
    al-=(n-x)*m
    #(2)
    if al<=0:
        return True
    s=x*b-sum(a[:x])
    #(3)
    if al>s:
        return False
    else:
        return True

while l+1<r:
    k=(l+r)//2
    if adopt(k):
        l=k
    else:
        r=k

if adopt(r):
    print(p+r)
else:
    print(p+l)

Code que je suis allé viser à la fois le plus court et le plus rapide après le concours ↓ (C'est devenu un code à moitié fini qui n'était ni très court ni précoce.)

answerB_better.py


n,m,v,p=map(int,input().split())
a=sorted(list(map(int, input().split())),reverse=True)[p-1:]
l,r=0,n-p
while l+1<r:
    k=(l+r)//2
    b=a[k]+m
    if b<a[0] or (v-(n-k))*m>(k*b-sum(a[:k])): r=k
    else: l=k
b=a[r]+m
print(p+l if(b<a[0] or (v-(n-r))*m>(r*b-sum(a[:r]))) else p+r)

Problème C

Je n'ai pas pu le résoudre pendant le concours. Selon la considération lors du concours, il est nécessaire d'égaliser le nombre de dominos placés verticalement et horizontalement, et s'ils sont égalisés, la qualité peut être fixée à 3 pour créer un agencement de dominos qui satisfont les conditions. Il s'avère (sauf quand n = 2,3). Ici, lorsque les dominos étaient disposés en tenant compte de la symétrie, lorsque n était un multiple de 3, nous avons pu trouver la disposition des dominos de qualité 1 en disposant les dominos verticalement et horizontalement dans l'ordre le long de la diagonale. Cependant, je ne pouvais pas trouver un arrangement hautement symétrique lorsque n n'était pas un multiple de 3 (** je devrais considérer une autre méthode ici **). Ainsi, ** les grands nombres fonctionnent souvent bien lorsqu'ils sont divisés **, alors pensez également à ce problème. En se concentrant sur la matrice carrée partielle de la i-ème ligne à la j-ème ligne et de la i-ème à la j-ème colonne, la partie de la i-ème ligne à la j-ème ligne et la i-ème à la j-ème colonne autre que cette matrice carrée est 0. Si c'est le cas, nous pouvons voir que la qualité de la matrice carrée partielle est de la ligne i à la colonne j et de la colonne i à la colonne j. Par conséquent, nous savons que nous devons construire une telle matrice carrée partielle. Compte tenu de la matrice dont la qualité est 3 ci-dessus, j'ai l'impression qu'elle semble se trouver dans une matrice carrée de 4ème ordre ou plus. De là, ** je ferai de mon mieux pour trouver une telle matrice carrée **. En regardant la méthode de Answer, j'ai trouvé une matrice carrée d'ordre 3,4,5,6,7, et divisé les cas avec mod4 pour le rendre carré. Vous pouvez organiser les matrices carrées dans l'ordre sur la diagonale de la matrice. (En comptant à partir du haut, c'est 4e, 4e, 4e, ..., (4or5or6or7) Il est aligné avec ce qui suit.) J'utilise mod6 pour classer les cas où n est un multiple de 3 car il y a un arrangement simple. Cependant, la méthode de résolution est probablement la méthode la plus simple car il est nécessaire de trouver une matrice carrée d'ordre 3,4,5,6,7,8.

answerC.py


n=int(input())

if n==2:
    print(-1)
else:
    x=[]
    if n%3==0:
        for i in range(n//3):
            x.append("."*(3*i)+"a"+"."*(n-3*i-1))
            x.append("."*(3*i)+"a"+"."*(n-3*i-1))
            x.append("."*(3*i)+".aa"+"."*(n-3*i-3))
    elif n%6==1:
        for i in range(n//6-1):
            x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
            x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
            x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
            x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
            x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
            x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
        x.append("."*(n-7)+".aab.c.")
        x.append("."*(n-7)+"d..b.c.")
        x.append("."*(n-7)+"d..eeff")
        x.append("."*(n-7)+"g..mm.l")
        x.append("."*(n-7)+"gnn...l")
        x.append("."*(n-7)+"h...kkj")
        x.append("."*(n-7)+"hii...j")
    elif n%6==2:
        for i in range(n//6-1):
            x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
            x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
            x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
            x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
            x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
            x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
        x.append("."*(n-8)+".a.bb.cc")
        x.append("."*(n-8)+".a...m.j")
        x.append("."*(n-8)+"..pp.m.j")
        x.append("."*(n-8)+"hh..i.o.")
        x.append("."*(n-8)+"gg..i.o.")
        x.append("."*(n-8)+"..n.ll.k")
        x.append("."*(n-8)+"f.n....k")
        x.append("."*(n-8)+"f.dd.ee.")
    elif n%6==4:
        for i in range(n//6):
            x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
            x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
            x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
            x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
            x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
            x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
        x.append("."*(n-4)+"aacb")
        x.append("."*(n-4)+"ffcb")
        x.append("."*(n-4)+"hgdd")
        x.append("."*(n-4)+"hgee")
    else:
        for i in range(n//6):
            x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
            x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
            x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
            x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
            x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
            x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
        x.append("."*(n-5)+"aabbc")
        x.append("."*(n-5)+"g.h.c")
        x.append("."*(n-5)+"gjh..")
        x.append("."*(n-5)+"dj.ii")
        x.append("."*(n-5)+"deeff")
    for i in range(n):
        print("".join(x[i]))

Problème après D

Je sentais que c'était encore à un niveau qui devrait être résolu, alors j'aimerais le remettre en question la prochaine fois que je le ferai.

Recommended Posts

AtCoder Grand Contest 041 Critique
AtCoder Grand Contest 048 Critique
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
AtCoder Grand Contest 046 Critique
Critique du concours AtCoder Beginner Contest 152
Revue du concours régulier AtCoder 105
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Revue du concours régulier AtCoder 104
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
AtCoder Grand Contest 041 Rapport de participation
AtCoder Grand Contest 040 Rapport de participation
AtCoder Grand Contest 047 Rapport de participation
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Défi des questions passées 1
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 177
concours yukicoder 259 avis
concours yukicoder 264 avis
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
concours yukicoder 261 avis
concours yukicoder 267 avis
Concours AtCoder Débutant 173
concours yukicoder 266 avis
Concours Atcoder Débutant 153
concours yukicoder 263 avis
yukicoder contest 268 avis
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes