[PYTHON] AtCoder Beginner Contest 089 Revue des questions précédentes

Temps requis

Impressions

C'est une question passée que j'ai déjà résolue, mais j'ai refait la même erreur dans le problème D. Les détails de l'erreur sont mentionnés dans la section problème D.

Problème A

C'est un groupe de 3 personnes, vous pouvez donc le diviser par 3.

answerA1.py

print(int(input())//3)

Problème B

Tout ce que vous avez à faire est de compter le nombre de couleurs et d'utiliser set pour éliminer les doublons.

answerB.py

n=int(input())
s=input().split()
print("Three" if len(set(s))==3 else "Four")

Problème C

Tout d'abord, vérifiez combien de noms commencent par chaque lettre. De plus, si vous sélectionnez trois caractères de départ, vous pouvez savoir combien il y en a lorsque vous sélectionnez ces trois caractères en multipliant le nombre de noms commençant par chaque caractère. Et comme il existe $ _5C_3 $ façons de choisir le personnage de départ, vous pouvez réfléchir au nombre de façons de choisir les trois personnes dans le sujet en trouvant la somme.

answerC.py

import itertools
n=int(input())
s=dict()
for i in ["M","A","R","C","H"]:
    s[i]=0
for i in range(n):
    _s=input()
    if _s[0] in ["M","A","R","C","H"]:
        s[_s[0]]+=1
s=list(s.items())
ans=0
for i in range(5):
    for j in range(i+1,5):
        for k in range(j+1,5):
            ans+=(s[i][1]*s[j][1]*s[k][1])
print(ans)

Problème D

Vous pouvez voir que vous êtes susceptible d'utiliser la ** somme cumulée ** car vous devez traiter plusieurs ** requêtes d'intervalle **. De plus, il est nécessaire de considérer ** la somme cumulée des pouvoirs magiques **, mais comme le reste de $ R_i $ et $ L_i $ divisé par D est égal, ** ce qui arrive à la somme cumulée des pouvoirs magiques avec le reste de chaque nombre * Considérer *. Tout d'abord, j'ai pensé à stocker l'index de chaque cellule dans le tableau (num) séparément pour chaque reste écrit dans la cellule, mais ** il n'est pas nécessaire de le stocker séparément ** (le reste dans la somme cumulée) J'ai remarqué après la mise en œuvre que [Writer solution](voir https://img.atcoder.jp/abc089/editorial.pdf) pour plus de détails. De plus, dans l'implémentation ici, ceux avec des restes i = 1 à d-1 sont stockés dans le i-1er tableau imbriqué, ceux avec i = 0 sont stockés dans le d-1th, etc. ** Traitement d'index C'était très gênant **. Ici, les informations des carrés sont stockées dans le tableau divisé par le reste des nombres, donc à partir de là, nous allons stocker la somme cumulée de la puissance magique dans un autre tableau (mp). Le calcul de la puissance magique est simplement calculé à partir de la distance de Manhattan. Si vous pouvez trouver cette somme cumulée, vous pouvez afficher la puissance magique totale correspondant à la requête. De plus, la puissance magique cumulée nécessaire pour passer de `num [g] [0]` à num [g] [k] `est` `mp [g] [k]` Notez que puisqu'il s'agit de, il faut afficher `mp [g] [f] -mp [g] [e]` quand `ʻe! = 0``` ..

answerD.py

from math import ceil
h,w,d=map(int,input().split())
x=ceil((h*w)/d)
num=[[[-1,-1] for j in range(x)] for i in range(d)]#Cas de trop(1→0)
mp=[[0]*x for i in range(d)]
a=[list(map(int,input().split())) for i in range(h)]
for i in range(h):
    for j in range(w):
        k,l=a[i][j]%d,a[i][j]//d
        if k==0:
            num[d-1][l-1]=[i,j]
        else:
            num[k-1][l]=[i,j]
for i in range(d):
    for j in range(x):
        if j!=x-1:
            if num[i][j+1]!=[-1,-1]:
                mp[i][j+1]+=(mp[i][j]+abs(num[i][j+1][0]-num[i][j][0])+abs(num[i][j+1][1]-num[i][j][1]))
            else:
                break
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    if l%d!=0:
        e,f=l//d,r//d
    else:
        e,f=l//d-1,r//d-1
    g= d-1 if l%d==0 else l%d-1
    if e==0:
        print(mp[g][f])
    else:
        print(mp[g][f]-mp[g][e])