A participé virtuellement au concours AtCorder pour débutants 153. C'était la question AC de l'ABCD. J'utilise Python3.
Compte tenu du nombre d'attaques dont la force physique du monstre sera de 0 ou moins, je pense qu'il est nécessaire de trouver le quotient de division. Cependant, il est étrange que le nombre de fois ne soit pas un entier, donc si le quotient de la division prend une fraction, il est nécessaire de répondre à l'entier porté.
H, A = map(int,input().split())
if H % A == 0:
print(H // A)
else:
print(H // A + 1)
S'il était arrondi, je n'avais pas besoin d'utiliser l'instruction if.
import math
H, A = map(int,input().split())
print(math.ceil( H // A ))
Vous pouvez gagner si la force physique qui peut être réduite par tous les mouvements spéciaux est supérieure à la force physique du monstre.
H, N = map(int,input().split())
A = list(map(int,input().split()))
if sum(A) >= H:
print("Yes")
else:
print("No")
Je voudrais utiliser le mouvement spécial qui réduit la force physique du monstre à 0 pour les monstres à forte force physique. Par conséquent, arrangez les monstres par ordre décroissant de force physique et battez K monstres avec un coup spécial. Puisque les monstres N -K restants sont vaincus en attaquant, il est nécessaire d'attaquer autant de fois que la force physique totale de ce monstre N -K.
N, K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
del A[:K]
print(sum(A))
Au début, lisez l'énoncé du problème qu'il y a un monstre avec une force physique H. Répétez l'opération de réduction du nombre de monstres dont la force physique est divisée par deux d'une attaque à deux (les valeurs après la virgule décimale sont tronquées). Si la santé H du monstre n'est pas une puissance de 2, alors H a une fraction impaire. Par conséquent, le point décimal est tronqué dans le processus de réduction de moitié de la force physique, et la force physique totale est réduite simplement en divisant le monstre. Par conséquent, je pensais que le nombre d'attaques changerait si la force physique H était une puissance de 2.
À partir de là, nous allons en fait effectuer des calculs numériques et en tirer une théorie générale.
H Nombre d'attaques 1 1 fois 2 ~ 3 3 fois 4 ~ 7 7 fois 8 ~ 15 15 fois Lorsque H est compris entre 2 n </ sup> et 2 n + 1 </ sup> -1, le nombre d'attaques est de 2 0 </ sup> à 2 n </ sup> Vous pouvez voir qu'il peut être exprimé par la somme de jusqu'à.
Considérons maintenant si H est compris entre 2 à la nième puissance et 2 à la n + 1ère puissance. Il est calculé en convertissant un nombre décimal en nombre binaire et en comptant le nombre de caractères.
H = int(input())
n = len(bin(H)) - 3
N = [2 ** i for i in range(n + 1)]
print(sum(N))
Lorsque H est compris entre 2 n </ sup> et 2 n + 1 </ sup> -1, le nombre d'attaques peut être exprimé par 2 n + 1 </ sup> -1. De plus, n a été obtenu en prenant un journal avec une base de 2 et en le tronquant après la virgule décimale.
import math
H = int(input())
n = math.floor(math.log2(H))
print(2 ** (n + 1) -1)
Apparemment, c'était un problème célèbre de sacs à dos en nombre limité. Je ne comprenais pas du tout la DP (méthode de planification dynamique), alors j'ai utilisé cela comme référence. Facile à comprendre.
https://qiita.com/drken/items/dc53c683d6de8aeacf5a
Le premier est le résultat de devenir TLE. (AC pour Pypy3) Considérez le i-ème des N types de magie que vous pouvez utiliser. Si vous pouvez utiliser la i-ème magie pour réduire la force physique totale de j, le pouvoir magique épuisé est dp[j] = dp[j - a] + b Si vous pouvez réduire la force physique totale de j sans utiliser la magie i-ème, la puissance magique épuisée est dp[j] = dp[j] Ce sera. Comparez-les pour trouver la valeur minimale et utilisez-la comme dp [j]. Le nombre d'éléments de dp [] est H + max (force physique réductible) car la force physique du monstre est parfaite et il n'est pas nécessaire de le vaincre. La valeur initiale est dp [0] = 0 De plus, comme 0 est la valeur minimale, la casse est divisée par l'instruction if.
H, N= map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
A[i], B[i] = map(int, input().split())
ma = max(A)
dp = [0] * (H + ma)
dp[0] = 0
for i in range(N):
a = A[i]
b = B[i]
for j in range(1, H + ma):
if dp[j] == 0:
dp[j] = dp[j - a] + b
else:
dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))
Je regrette que l'instruction if semble être lente dans la boucle double for et l'a améliorée, mais c'est TLE. (AC pour Pypy3) Puisqu'il est fait en mettant l'infini dans l'élément de dp [], il n'est pas nécessaire de juger par cas. C'est plus facile à voir, mais cela prend plus de temps que la première réponse.
H, N= map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
A[i], B[i] = map(int, input().split())
ma = max(A)
dp = [float("inf")] * (H + ma)
dp[0] = 0
for i in range(N):
a = A[i]
b = B[i]
for j in range(1, H + ma):
dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))
Je veux AC avec Python.
Gingitsune combat N monstres. Les monstres sont alignés dans une rangée et peuvent être considérés comme étant sur un certain nombre de lignes droites. Le i-ème monstre est à la coordonnée Xi et a Hi. Gingitsune peut utiliser des bombes pour attaquer des monstres. L'utilisation d'une bombe à la coordonnée x peut réduire la santé de tous les monstres dans la plage x − D ou plus et x + D ou moins de A. Vous ne pouvez pas réduire la force d'un monstre sauf en utilisant une bombe. Si la force physique de tous les monstres est définie sur 0 ou moins, le gingitsune gagne. Trouvez le nombre minimum de fois qu'un gingitsune utilisera une bombe pour battre un monstre.
L'échantillon donne le résultat correct, mais c'était WA. Organisez les distances par ordre croissant et attaquez jusqu'à ce que la plus petite valeur devienne 0. J'ai donc pensé que je réduirais la force physique des monstres à portée pour être attaqués en même temps et recréerais la liste.
import math
N, D, A= map(int,input().split())
X = [0] * N
H = [0] * N
Y = []
for i in range(N):
X[i], H[i] = map(int, input().split())
Y.append([X[i] ,math.ceil(H[i] / A)])
Y.sort()
d = 0
while len(Y) > 0:
y_min = Y[0][1]
c = 0
d += y_min
for i in range(len(Y)):
if Y[i][0] < Y[0][0] + 2 * D + 1:
Y[i][1] = Y[i][1] - y_min
if Y[i][1] <= 0:
c += 1
del Y[0:c]
print(d)
Recommended Posts