[PYTHON] AtCoder Débutant Contest 161 Critique

Les résultats de cette fois

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.

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