[PYTHON] 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
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