Virtually participated in AtCorder Beginner Contest 153. It was ABCD's 4 question AC. I'm using Python3.
Considering how many attacks the monster's health will be below 0, I think it is necessary to find the quotient of division. However, it is strange that the number of times is not an integer, so if the quotient of division takes a decimal, you need to answer the rounded integer.
H, A = map(int,input().split())
if H % A == 0:
print(H // A)
else:
print(H // A + 1)
It was good not to use the if statement when rounding up the decimal point.
import math
H, A = map(int,input().split())
print(math.ceil( H // A ))
You can win if the physical strength that can be reduced by all special moves is greater than the physical strength of the monster.
H, N = map(int,input().split())
A = list(map(int,input().split()))
if sum(A) >= H:
print("Yes")
else:
print("No")
I would like to use the special move that reduces the monster's health to 0 for monsters with high health. Therefore, arrange the monsters in descending order of physical strength, and defeat K monsters with a special move. Since the remaining N --K monsters are defeated by attacking, it is necessary to attack as many times as the total health of these N --K monsters.
N, K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
del A[:K]
print(sum(A))
At first, read from the problem statement that there is one monster with H health. Repeat the operation of halving the health of two monsters with one attack (rounding down the values after the decimal point). If the monster's health H is not a power of 2, H has an odd number of divisors. Therefore, the decimal point is cut off in the process of halving the physical strength, and the total physical strength is reduced only by splitting the monster. Therefore, I thought that the number of attacks would change if the physical strength H was a power of 2.
From here, we will actually perform numerical calculations and derive general theory.
H Number of attacks 1 1 time 2 ~ 3 3 times 4 ~ 7 7 times 8 ~ 15 15 times When H is from 2 n </ sup> to 2 n + 1 </ sup> -1, the number of attacks is from 2 0 </ sup> to 2 n </ sup> You can see that it can be expressed by the sum of up to.
Now consider whether H is between 2 to the nth power and 2 to the n + 1th power. It is calculated by converting a decimal number to a binary number and counting the number of characters.
H = int(input())
n = len(bin(H)) - 3
N = [2 ** i for i in range(n + 1)]
print(sum(N))
When H is from 2 n </ sup> to 2 n + 1 </ sup> -1, the number of attacks can be expressed as 2 n + 1 </ sup> -1. In addition, n was obtained by taking a log with a base of 2 and truncating it to the nearest whole number.
import math
H = int(input())
n = math.floor(math.log2(H))
print(2 ** (n + 1) -1)
Apparently, it was a famous problem of limited number knapsacks. I didn't understand DP (Dynamic Programming) at all, so I used this as a reference. Easy to understand.
https://qiita.com/drken/items/dc53c683d6de8aeacf5a
First is the result of becoming TLE. (AC for Pypy3) Consider the i-th of the N types of magic you can use. If you can use the i-th magic to reduce the total health by j, the consumed magic power is dp[j] = dp[j - a] + b If you can reduce the total health by j without using the i-th magic, the exhausted magic power is dp[j] = dp[j] It will be. Compare these to find the minimum value and use it as dp [j]. The number of elements of dp [] is H + max (reducable health) because the monster's health is perfect and there is no need to defeat it. The initial value is dp [0] = 0 Also, since 0 is the minimum value, the case is divided by the if statement.
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:]))
I regret that the if statement seems to be slow in the double for loop and improved it, but it is TLE. (AC for Pypy3) Since it is made by putting infinity in the element of dp [], it is not necessary to judge by case. It's easier to see, but it takes longer than the first answer.
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:]))
I want to AC with Python.
The red fox is fighting N monsters. The monsters are lined up in a row and can be considered to be on a number line. The i-th monster is at coordinates Xi and has a health of Hi. The red fox can use bombs to attack monsters. Using a bomb at coordinate x can reduce the health of all monsters in the range x−D and above x + D and below by A. You can't reduce a monster's health except by using a bomb. If all monsters have less than 0 health, the red fox wins. Find the minimum number of times a red fox will use a bomb to beat a monster.
The sample gives the correct result, but it was WA. Arrange the distances in ascending order and attack until the smallest value becomes 0. Therefore, I thought that I would reduce the physical strength of the monsters in the range to be attacked at the same time and recreate the list.
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