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

Temps requis

スクリーンショット 2020-04-11 10.34.05.png

Impressions

Il a fallu un temps inhabituel pour écrire un DP normal (problème C) et j'ai mal lu la phrase du problème (problème D). Je ne vois pas d'autre solution que de me calmer ... Aujourd'hui, le déroulement du concours → examen était relativement fluide, donc je ferai de mon mieux pour résoudre le concours et le réviser tous les jours.

Problème A

Cela a pris beaucoup de temps parce que je pensais que je devais sortir les nombres après cela, même si je n'avais qu'à sortir ABD ou ACD.

answerA.py


n=int(input())
x=n-999 if n>999 else n
if n>999:
    print("ABD")
else:
    print("ABC")

Problème B

Compte tenu de la différence entre les tours adjacentes, la différence entre la tour i + 1st et la tour i-th est de i + 1, donc soustrayez b de la hauteur de la tour de bain ou de la tour ba-1st. Il suffit de soustraire a de la hauteur.

answerB.py


a,b=map(int,input().split())
k=b-a
print(((1+k)*k)//2-b)

Problème C

Premièrement, lorsqu'il y a le nombre minimum d'opérations **, même si l'opération est remplacée, le nombre de fois reste le minimum **, donc l'opération de retrait de 1 yen est utilisée pour un ajustement jusqu'à N yen. Ici, l'opération pour extraire la puissance de 6 de n <= 100000 est $ 6 ^ 1… 6 ^ 6 $, et l'opération pour extraire la puissance de 9 est $ 9 ^ 1… 9 ^ 5 $. Il y a 5 façons (9 $ ^ 6> 100000 $). Par conséquent, j'ai réfléchi à la manière de sélectionner l'opération en autorisant la duplication, et si elle était inférieure à n, je pensais qu'elle serait compensée par 1. On peut donc l'obtenir par O (n) en considérant ** DP uniquement **, l'opération de prélèvement de la puissance de 6 → l'opération de prélèvement de la puissance de 9. De plus, lors de la recherche de la valeur minimale avec DP, inf est entré comme valeur initiale dans le tableau préparé, mais k yen (k <= n) peut être exprimé en utilisant k boules de 1 yen, de sorte que la valeur initiale La valeur initiale i est attribuée là où l'indice est i.

answerC.py


import math
n=int(input())
l1=math.floor(math.log(n,6))
l2=math.floor(math.log(n,9))
dp=[i for i in range(n+1)]
for i in range(1,l1+1):
    for j in range(n):
        if j+6**i<n+1:
            dp[j+6**i]=min(dp[j]+1,dp[j+6**i])
for i in range(1,l1+1):
    for j in range(n):
        if j+9**i<n+1:
            dp[j+9**i]=min(dp[j]+1,dp[j+9**i])
print(dp[-1])

Problème D

Tout d'abord, j'ai pensé que je pourrais repeindre plusieurs fois pour une cellule (car j'ai vu le problème que repeindre peut être fait plusieurs fois dans le problème de repeindre), mais cette fois, il n'est pas possible de repeindre plusieurs fois. Notez que vous ne pouvez pas ** (la partie commentaire). ** Veuillez noter qu'il y a un tel effet néfaste si vous le connectez immédiatement au problème ou à l'algorithme que vous avez résolu auparavant **. Premièrement, en d'autres termes, pour les grilles (i, j), les carrés avec le même mod3 de i + j ont la même couleur, mais les carrés avec différents mod3s de i + j ont des couleurs différentes. Par conséquent, afin de séparer les cas avec mod3 de i + j, ** stockez chaque valeur de mod3 de i + j dans le tableau g **. (1) Sur cette base, les couleurs des carrés seront réécrites dans l'ordre, mais si vous décidez de la couleur pour réécrire les carrés pour chacun des trois tableaux du tableau g, il y a $ 30 \ times29 \ times28 $, donc chacun d'eux Si vous réécrivez la couleur des carrés (500 $ \ times500 $), vous constaterez que vous ne pouvez pas le faire dans le temps imparti. Ici, nous avons décidé d'effectuer un prétraitement pour pré-calculer l'inconfort total lorsque chaque ** couleur carrée passera de 1 à C **. (2) De plus, il existe 30 $ \ times29 \ times28 $ façons, mais ** il n'est pas nécessaire de réécrire dans une couleur qui semble gênante lors de la réécriture **, il y a donc 3 façons dont l'inconfort est le moins pour chacun des trois tableaux contenus dans le tableau g Choisissez la couleur de (3) et trouvez la valeur minimale dans les manières $ 3 \ times3 \ times3 $ qui peuvent être le minimum du total (4).

answerD.py


n,c=map(int,input().split())
d=[list(map(int,input().split())) for i in range(c)]
c_=[list(map(int,input().split())) for i in range(n)]

#(1)
g=[[] for i in range(3)]
for i in range(n):
    for j in range(n):
        g[(i+j+2)%3].append(c_[i][j]-1)

'''
for i in range(c):
    for j in range(c):
        for k in range(c):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
print(d)
'''

#(2)
f=[[] for i in range(3)]
for i in range(3):
    for j in range(c):
        x=0
        for k in g[i]:
            x+=d[k][j]
        f[i].append((j,x))
    #(3)
    f[i]=sorted(f[i],key=lambda x:x[1])[:3]

#(4)
ans=[]
for i in f[0]:
    for j in f[1]:
        for k in f[2]:
            if i[0]!=j[0] and k[0]!=j[0] and i[0]!=k[0]:
                ans.append(i[1]+j[1]+k[1])
print(min(ans))

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 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
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 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 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 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 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
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes