[PYTHON] AtCoder Débutant Contest 161 Critique

Les résultats de cette fois

スクリーンショット 2020-04-05 11.06.28.png

Impressions de cette époque

L'ABC de la semaine dernière était une parade d'erreurs, mais cette semaine, cela a fonctionné. Je l'ai utilisé pendant environ 50 minutes à cause du problème D, et il semblait que je me contenterais de ma performance habituelle, alors je suis content d'avoir pu montrer ma ténacité. Il y a encore des problèmes tels que l'impossibilité de résoudre le problème E à temps, alors j'aimerais travailler plus dur.

Problème A

Il suffit de penser à la manière dont ils seront remplacés si vous effectuez les opérations dans l'ordre. J'ai également découvert qu'en définissant `` print (z, x, y) '', il est possible de sortir avec un espace entre z, x, y. Je souhaite l'utiliser à partir de maintenant.

A.py


x,y,z=map(int,input().split())
print(z,x,y)

Problème B

Puisque s est le nombre total de voix, il suffit de juger si le nombre de s / 4m ou plus est de m ou plus.

B.py


n,m=map(int,input().split())
b=list(map(int,input().split()))
s=sum(b)
a=[i for i in b if i>=s/(4*m)]
print("Yes" if len(a)>=m else "No")

Problème C

Si n est supérieur ou égal à k, remplacez n par n-k. Si n est inférieur ou égal à k, remplacez-le par k-n. De plus, si n est inférieur ou égal à k, n reste inférieur ou égal à k même s'il est remplacé par k-n. Par conséquent, le reste de la division par k ne change pas pendant la première opération, et ne change pas de n% k ou k-n% k pendant la deuxième opération. Par conséquent, vous pouvez afficher `` min (n% k, k-n% k) ''.

C.py


n,k=map(int,input().split())
n=n%k
print(min(n,k-n))

Problème D

Tout d'abord, j'écrivais un dendrogramme. En écrivant le dendrogramme, j'ai réalisé qu'il pouvait y avoir une relation entre le i-ème chiffre et le i + 1-ème chiffre **. Donc, quand j'ai expérimenté ** ce qui se passe entre le 1er et le 2ème chiffres **, c'est devenu comme suit.

IMG_0176.PNG

À partir du résultat de l'expérience, si le numéro d'exécution est traité comme une chaîne de caractères, si le ** nombre de "la valeur absolue de la différence entre le numéro d'exécution à i chiffres et le i-ème chiffre est égal ou inférieur à 1" est ajouté à l'arrière du numéro d'exécution à i chiffres. ** Vous pouvez voir que vous pouvez créer le numéro d'exécution dans le chiffre i + 1. De plus, comme vous pouvez le voir dans l'expérience ci-dessus, ** si le i-ème chiffre est 0 ou 9, il y a deux nombres à ajouter à la fin, sinon il y a trois types **. (✳︎) Par conséquent, effectuez l'opération ci-dessus pour chaque chiffre et stockez-le dans le tableau, ** lorsque le nombre total d'éléments contenus dans le tableau dépasse k, terminez l'opération ci-dessus ** et k dedans. Demandez simplement la seconde.

(✳︎)… Pendant le concours, je l'ai également ajouté au recto, donc j'ai supprimé les doublons avec set. Ceci est le premier code. Le deuxième code est le code ajouté uniquement au verso.

answerD.py


k=int(input())
ans=[[i for i in range(1,10)]]
d=9
while d<k:
    ans.append([])
    for i in ans[-2]:
        x=str(i)
        y=int(x[0])
        if y==1:
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        elif 2<=y<=8:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        else:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
        z=int(x[-1])
        if z==0:
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        elif 1<=z<=8:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        else:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
    ans[-1]=list(set(ans[-1]))
    d+=len(ans[-1])
l=len(ans[-1])
v=sorted([int(i) for i in ans[-1]])

print(v[k-(d-l)-1])

answerD_better.py


k=int(input())
ans=[[i for i in range(1,10)]]
d=9
while d<k:
    ans.append([])
    for i in ans[-2]:
        x=str(i)
        z=int(x[-1])
        ans[-1].append(x+str(z))
        if z<=8:
            ans[-1].append(x+str(z+1))
        if z>=1:
            ans[-1].append(x+str(z-1))
    d+=len(ans[-1])
ans[-1].sort()
print(ans[-1][k-d-1])

E problème

Je vois le commentaire. Je pense que c'est une bonne question à résoudre lorsque vous l'oubliez. Quand j'ai vu ce problème, j'ai eu une idée court-circuitée de l'intervalle → "imos ou somme cumulative". Je pense que réfléchir à la façon de résoudre un problème centré sur de tels ** algorithmes est une façon de penser qui vous empêche de devenir plus fort **, alors j'aimerais m'arrêter. Cette fois, je pense que c'était un problème qui sonnait un avertissement à une telle idée. C'est parce que ** toutes les bases utilisent l'algorithme lorsque vous souhaitez réduire la quantité de calcul par la méthode gourmande **. Ici, nous envisagerons d'utiliser la méthode gloutonne. (✳︎) Disons que nous allons considérer les jours où nous pouvons travailler en ordre de front pour ce problème. À ce moment ** Que signifie le i-ème jour ouvrable choisi **? Comme indiqué dans Réponse, c'est le premier jour que vous pouvez choisir lorsque vous choisissez le jour ouvrable de l'avant. En d'autres termes, ** la i-ème date de choix n'apparaît qu'après cette date **. Au contraire, ** En pensant aux jours ouvrables depuis l'arrière **, et le jème jour ouvrable sélectionné ** n'apparaît qu'avant ce jour **. Notez également que le jème jour à compter de l'arrière est le k-j + 1er jour à compter de l'avant car il ne fonctionne que k jours. À partir de ce qui précède, nous avons obtenu l'information selon laquelle la i-ième date sélectionnée du front doit être ** x jours ou plus tard et y jours ou plus tôt **. Si x <y, il y a plusieurs candidats pour le i-ème jour, mais si ** x = y, il n'y a pas de candidats autres que x (= y) pour le i-ème jour **. Par conséquent, vous pouvez trouver la réponse en comptant les jours pendant lesquels vous pouvez travailler dans l'ordre de l'avant et de l'arrière, et en ne sortant que lorsque le i-ème jour ouvrable de l'avant est le même. Je suis convaincu de ce problème, et il semble que je puisse le reproduire si un problème similaire se produit, mais c'était un problème que je voulais aborder à première vue. Je n'ai pas eu assez de temps pour voir la réponse après le concours, et j'ai été déçu, alors je voudrais faire un effort ** pour accélérer globalement ** afin de pouvoir résoudre les six questions fermement.

(✳︎)… La méthode gloutonne n'est pas un algorithme.

answerE.py


n,k,c=map(int,input().split())
s=input()
l=[-1]*k
r=[-1]*k
nowl=0
indl=0
while nowl<n and indl<k:
    for i in range(nowl,n):
        if s[i]=="o":
            l[indl]=i
            nowl=i+c+1
            indl+=1
            break
nowr=n-1
indr=k-1
while nowr>=0 and indr>=0:
    for i in range(nowr,-1,-1):
        if s[i]=="o":
            r[indr]=i
            nowr=i-c-1
            indr-=1
            break
for i in range(k):
    if l[i]==r[i]:
        print(l[i]+1)

Problème F

Supposons que $ k (\ neq $ 1) soit une fraction de ** n **. Ici, ** n est divisé par k jusqu'à ce qu'il devienne indivisible par k **, puis ** n est remplacé par nk ** (n mod k reste inchangé $ \ leftrightarrow $ n reste indivisible par k). Devenir. Par conséquent, si vous pensez de la même manière que le problème C, vous pouvez dire que ** n mod k vaut 1 et finalement n devient 1 **. De plus, si ** k n'est pas une fraction de n, vous ne pouvez remplacer n que par n-k **, il vous suffit donc de vérifier si n mod k vaut 1. De plus, n mod k devient 1 car l * k + 1 = n $ \ leftrightarrow $ l * k = n-1 lorsque l'opération de remplacement de n par nk est effectuée l fois. Vous pouvez voir que ** k doit être une fraction de n-1 **. (✳︎) De ce qui précède, dans le code ci-dessous, reportez-vous au code de make_divisors (je n'ai pas préparé le code pour énumérer le nombre de nombres par moi-même, donc cet article) Après avoir trouvé toutes les fractions entre (), le n mod k ci-dessus a été vérifié avec chaque fraction comme k. Quand j'ai vérifié à nouveau le code que j'ai écrit pendant le concours, j'ai trouvé que le code avait été écrit de manière assez appropriée, donc je voudrais ** l'examiner attentivement avant d'écrire le code.

(✳︎)… Lorsque k n'est pas une fraction de n, on peut montrer par la méthode de l'absurdité que k est une fraction de n-1.

answerF.py


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
n=int(input())
x=make_divisors(n)
l=len(x)
ans=0
for i in range(l):
    k=n
    if x[i]==1:
        continue
    while k%x[i]==0:
        k//=x[i]
    if k%x[i]==1:
        ans+=1

y=make_divisors(n-1)
l2=len(y)
ans2=0
for i in range(l2):
    k=n
    if y[i]==1:
        continue
    while k%y[i]==0:
        k//=y[i]
    if k%y[i]==1:
        ans2+=1
print(ans+ans2)

answerF_better.py


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def all_pattern(l):
    global n
    ans=0
    for ds in make_divisors(l)[1:]:
        k=n
        while k%ds==0:
            k//=ds
        ans+=(k%ds==1)
    return ans

n=int(input())
print(all_pattern(n)+all_pattern(n-1))

Recommended Posts

Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
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
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
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
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 181 Remarque
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Concours AtCoder Débutant 180 Remarque
Concours AtCoder Débutant 182 Remarque
AtCoder Grand Contest 048 Critique
Concours AtCoder pour débutants 156 WriteUp
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Concours AtCoder pour débutants 167
Concours AtCoder Débutant 183 Remarque
AtCoder Regular Contest 106 Évaluation
Concours AtCoder Débutant 184 Remarque
AtCoder Grand Contest 046 Critique
Revue du concours régulier AtCoder 104
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
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes