AtCoder Beginner Contest 089 Revue des questions précédentes

Temps requis

スクリーンショット 2020-04-01 16.39.23.png

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

Recommended Posts

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 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
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes