[PYTHON] AtCoder Débutant Contest 162 Évaluation

Les résultats de cette fois

Impressions de cette époque

Ce n'est pas mal en termes de performances, mais je suis vraiment désolé car je n'ai pas pu résoudre à la fois E et F (même si cela a pris une heure). Pour le moment, je voudrais revenir sur ce qui manquait à E et F.

Problème A

Le fait que 7 soit inclus ou non peut être traité comme une chaîne de caractères. Pourquoi vous convertissez-vous en liste? Je suis trop fou.

A.py

n=list(input())
print("Yes" if "7" in n else "No")

Problème B

Vous devriez penser au total des choses qui ne se cassent pas même si 3 ou 5. Cela a pris quelques minutes car j'ai défini i% 3 == 0 et i% 5 == 0. ** Si cela ne fonctionne pas, cela ne fonctionne pas depuis le début **. Je voudrais résoudre ce problème lors du prochain concours.

B.py

ans=0
n=int(input())
for i in range(1,n+1):
    if i%3!=0 and i%5!=0:
        ans+=i
print(ans)

Problème C

J'ai émis WA ... Vous pouvez comprendre que cela ne passera que si vous réfléchissez calmement et réfléchissez un peu. ** Vous pouvez voir le résultat de gcd (i, j) au moment de la double boucle externe **, donc si vous calculez gcd (i, j) dans la boucle la plus interne, il sera calculé davantage et ce sera à temps pour la limite de temps ne pas. (J'étais trop impatient pendant le concours et je l'ai passé en C ++, mais cela passe aussi normalement en Python.)

C_TLE.py

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans+=gcd(gcd(i,j),l)
print(ans)

C.py

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)

Problème D

J'ai également résolu le problème D avec beaucoup d'impatience. Après tout, il se peut que ** si vous y mettez trop d'efforts, cela échouera au contraire **. La première chose qui est facile à comprendre à partir de ce problème est que les trois lettres à choisir sont ** R, G et B, respectivement **. De plus, comme la relation entre les index de chaque caractère devient un problème, j'ai décidé de stocker les index des ** caractères R, G et B séparément dans un tableau **. De plus, si vous pensez de la manière la plus courte sous ceci, vous devez décider dans l'ordre de r → g → b et considérer si l'index satisfait le thème. Cependant, ** Si rien n'est fait, N <= 4000 se traduira par O ($ N ^ 3 ) et il ne se terminera pas dans le délai **. Ici, puisque l'opération pour déterminer l'indice de R et G est O ( N ^ 2 $), j'ai pensé que ** les candidats pour l'indice du B restant devraient être déterminés par O (1) **. Ensuite, si le plus petit des index de R et G est x et le plus grand est y, les indices restants ** qui ne sont pas candidats pour l'indice de B sont x- (yx) '',. Vous pouvez voir qu'il y a trois manières de x + (yx) '', (x + y) / 2 (la régularité de x et y est la même) '' (taille d'index de R, G, B) Il a été trouvé en illustrant la relation entre les deux.) Une fois que vous savez cela, vous pouvez trouver la réponse en gérant l'index de B avec set et en soustrayant uniquement l'index qui n'est pas un candidat.

answerD.py

n=int(input())
s=input()
r,g,b=[],[],[]
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    else:
        b.append(i)
b=set(b)
lb=len(b)
ans=0
for i in r:
    for j in g:
        x,y=min(i,j),max(i,j)
        ans_=lb
        if x-(y-x) in b:
            ans_-=1
        if y+(y-x) in b:
            ans_-=1
        if (x%2==y%2) and (y-x)//2+x in b:
            ans_-=1
        ans+=ans_
print(ans)

E problème

Dans la continuité de la dernière fois, les problèmes E et F étaient très instructifs, donc cela vaut la peine d'être étudié. Si cette bande de niveau (bleu clair, bleu) peut être résolue de manière stable, il semble que les résultats seront stables, je voudrais donc résoudre les problèmes dans cette bande de niveau autant que possible. Dans ce problème, nous considérons gcd de la combinaison de $ K ^ N $, donc nous pouvons voir que ** tout compter n'est pas dans le temps **. Par conséquent, considérons le nombre de ** valeurs pgcd **. Aussi, puisque la valeur de gcd est 1 ~ k selon la définition de gcd, cherchez la séquence $ A_1, A_2,…, A_n $ où gcd est x ($ 1 \ leqq x \ leqq k $). Ici, la condition nécessaire et suffisante ** pour que ** gcd soit un multiple de x est ** $ A_1, A_2,…, A_n $ est un multiple de x **, donc $ (k // x) ^ Il y a n $ rues. Cependant, la condition nécessaire et suffisante ** pour que ** gcd soit exactement x est qu'il soit un multiple de ** x et non 2x, 3x,… **. Par conséquent, pour trouver le nombre de cas où pgcd est x, nous devons soustraire les cas où pgcd est 2x, 3x, ... de $ (k // x) ^ n $. Cependant, si vous déplacez x de 1 à k, vous devrez vérifier si 2x, 3x, ... est inférieur ou égal à k et soustraire le nombre dans ce cas. Dans ce cas ** 2x, 3x, Le nombre de cas de ... n'est pas toujours fixe **. Une idée efficace ici est de penser à ** x dans l'ordre inverse de k → 1 au lieu de 1 → k **. Dans ce cas, il peut être calculé en calculant d'abord combien de séquences de nombres telles que pgcd est 2y, 3y, ... et en soustrayant des candidats de la séquence de nombres tels que pgcd soit y. Aussi, puisque nous voulons considérer y pour lequel $ x = l \ times y (l \ geqq 1) $ vaut, il est facile de voir que ** y est une fraction de x **. De ce qui précède, en ce qui concerne le nombre de candidats dans la séquence de nombres lorsque pgcd est d'environ $ x_1, x_2,…, x_m $ de y excluant y lui-même, il suffit de soustraire le nombre de candidats dans la séquence de y en pgcd. En les mettant en œuvre, cela ressemble à ceci: De plus, la réponse est que vous devez trouver le reste de $ 10 ^ 9 + 7 $, et lors de l'initialisation du tableau mémo, spécifiez $ 10 ^ 9 + 7 $ comme troisième argument de pow pour $ 10 ^ 9 + 7 $. Il est également important de noter que le calcul peut être accéléré en demandant trop.

answerE.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,k=map(int,input().split())
mod=10**9+7
memo=[pow(k//i,n,mod) for i in range(1,k+1)] #pgcd est 1~Notez quand il devient k
for i in range(k-1,-1,-1):
    x=make_divisors(i+1)
    for j in x:
        if j!=i+1:
            memo[j-1]-=memo[i]
ans=0
for i in range(k):
    ans+=(memo[i]*(i+1))
    ans%=mod
print(ans)

Problème F

J'étais tellement habitué à la forme du sac à dos DP que je n'ai pas remarqué la transition d'état DP (ce n'est pas le nom officiel car je l'appelle simplement comme ça). ** J'ai essayé de le résoudre comme un puzzle dans les nuages sombres ** et je n'ai pas compris. Des problèmes comme celui-ci peuvent être ** étonnamment visibles avec un peu d'abstraction **. Premièrement, puisque la limite supérieure du nombre qui peut être sélectionné est n // 2, n'y a-t-il pas une limite supérieure au nombre qui peut être sélectionné jusqu'au ** i ème (i = 1,2, ..., n)? Il est important d'avoir la question **. Par conséquent, sur la base de cette question, ** le nombre de nombres adjacents ne peut pas être sélectionné **, donc on peut voir que le nombre qui peut être sélectionné du 1er au i-ème est (i + 1) // 2 ou moins. En outre, le nombre qui peut être sélectionné de i + 1 au nième est (n-i + 1) // 2 ou moins, et seul n // 2 est sélectionné de 1 à n, de sorte que le nombre qui peut être sélectionné du 1er au ième est Nécessite également la condition que n // 2- (n-i + 1) // 2 = (i-1) // 2 ou plus. Par conséquent, la condition selon laquelle ** le nombre de nombres à sélectionner jusqu'au i-ième doit être (i-1) // 2 ou plus (i + 1) // 2 ou moins ** est obtenue. Maintenant que nous savons qu'il y a une limite au nombre de nombres pouvant être sélectionnés jusqu'au i-ième, ** la relation entre le nombre de nombres pouvant être sélectionnés jusqu'au i-ème et le nombre pouvant être sélectionné jusqu'au i-ème ** et ** Il semble naturel de venir avec l'idée de considérer la relation entre le nombre de nombres sélectionnés jusqu'au i-ième et le nombre de nombres sélectionnés jusqu'au i + 1 **.

Figure 1

Figure 2

figure 3

Les figures 1 à 3 ci-dessus sont écrites sur la base de cette idée. Premièrement, sur la figure 1, le nombre de nombres sélectionnables dans le i-ème est montré dans l'ordre à partir du premier (la figure 2 est dans l'ordre à partir de la seconde). J'ai essayé de préparer une séquence DP qui préserve les deux états tels quels, mais comme cela ne correspondait pas à l'exemple de cas, j'ai regardé de près et j'ai trouvé que seuls ces deux états ** sauf lorsque deux nombres sont consécutifs * * Je n'ai pas pu. Autrement dit, sur la figure 1, la flèche rouge avance de 0 à 1 à 1, mais pas de 0 à 1 à 2. A l'inverse, pour la flèche bleue, vous pouvez procéder à la fois en 1 → 1 → 1 et 1 → 1 → 2. Il en va de même pour la figure 2. Pour la flèche rouge, 1 → 1 → 1 et 1 → 1 → 2 peuvent être avancés, mais pour la flèche jaune, seulement 0 → 1 → 1 peut être avancé, mais 0 → 1 → 2 Je ne peux pas continuer. Par conséquent, sur la figure 1, pour le deuxième 0,1 **, augmentez l'état de un ** à 0,1,1 et le premier 1 est le deuxième si le deuxième nombre n'est pas sélectionné. 1 devrait être le cas si vous choisissez le deuxième nombre. De plus, sur la figure 2, le troisième 1, 2 est 1, 2, 1, 2, le premier 1 est lorsque le troisième nombre n'est pas sélectionné, et le second 1 est lorsque le troisième nombre est sélectionné. Tu peux le faire. La figure 3 résume ce qui précède. Si vous regardez attentivement la figure 3, vous pouvez voir que ** la flèche pointe vers différents points selon que l'index est pair ou impair **. Cependant, si vous ne sélectionnez pas le i-ème nombre à ce moment, il s'écrit 1 si vous le sélectionnez avec $ \ pm $ 0, et vous devez vérifier si → est fermé selon cette notation. En mettant en œuvre les étapes ci-dessus docilement, cela devient comme suit. Veuillez noter que la sortie est différente lorsque n est pair et quand il est impair.

Pour reformuler ce que vous devez penser jusqu'à présent,

(1) Faites attention au type de contrainte (limite supérieure) il y a comme le nombre de nombres jusqu'au i-ème

(2) Dérivez que le nombre de nombres pouvant être sélectionnés jusqu'au i-ième est de deux.

(3) Expérimenter en faisant attention à la relation entre avant et après le i-ème (i-1er et i + 1)

(4) Notez qu'il y a 2 nombres différents jusqu'au i-ème, mais 3 états différents.

(5) Le mode de transition d'état diffère en fonction de la régularité de l'indice

On considère qu'il y en a cinq. Personnellement, je pensais que (1) était difficile à remarquer, mais ** considérant que la limite du nombre de pièces jusqu'au nième est n // 2 ou moins, je pense que ce n'est pas une barrière qui ne peut être dépassée. Je voudrais me consacrer et le saisir sensuellement.

answerF.py

n=int(input())
a=list(map(int,input().split()))
minf=-10000000000000
x=[[0,0,0] for i in range(n)]
x[0]=[0,0,a[0]]
for i in range(n-1):
    if i%2==0:
        x[i+1]=[max(x[i][0],x[i][1]),x[i][2],x[i][0]+a[i+1]]
    else:
        x[i+1]=[max(x[i][1],x[i][2]),x[i][0]+a[i+1],x[i][1]+a[i+1]]
print(max(x[-1][1],x[-1][2]) if n%2==0 else max(x[-1][0],x[-1][1]))