Praktisch am AtCorder Beginner Contest 153 teilgenommen. Es war ABCDs 4 Fragen AC. Ich benutze Python3.
Da wir überlegen, wie viele Angriffe die physische Stärke des Monsters 0 oder weniger betragen wird, halten wir es für notwendig, den Teilungsquotienten zu finden. Es ist jedoch seltsam, dass die Anzahl der Male keine Ganzzahl ist. Wenn also der Quotient der Division einen Bruchteil nimmt, muss die übertragene Ganzzahl beantwortet werden.
H, A = map(int,input().split())
if H % A == 0:
print(H // A)
else:
print(H // A + 1)
Wenn es aufgerundet wurde, musste ich die if-Anweisung nicht verwenden.
import math
H, A = map(int,input().split())
print(math.ceil( H // A ))
Sie können gewinnen, wenn die physische Stärke, die durch alle Spezialbewegungen verringert werden kann, größer ist als die physische Stärke des Monsters.
H, N = map(int,input().split())
A = list(map(int,input().split()))
if sum(A) >= H:
print("Yes")
else:
print("No")
Ich möchte den Spezialzug verwenden, der die physische Stärke des Monsters für Monster mit hoher physischer Stärke auf 0 reduziert. Ordne die Monster daher in absteigender Reihenfolge ihrer körperlichen Stärke an und besiege K Monster mit einem Spezialzug. Da die verbleibenden NK-Monster durch Angriffe besiegt werden, muss so oft angegriffen werden wie die gesamte physische Stärke dieses NK-Monsters.
N, K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
del A[:K]
print(sum(A))
Lesen Sie zunächst aus der Problemstellung, dass es ein Monster mit körperlicher Stärke H gibt. Wiederholen Sie den Vorgang, um die Anzahl der Monster zu reduzieren, deren physische Stärke durch einen Angriff auf zwei halbiert wird (Werte nach dem Dezimalpunkt werden abgeschnitten). Wenn die Gesundheit H des Monsters keine Potenz von 2 ist, hat H einen ungeraden Bruchteil. Daher wird der Dezimalpunkt beim Halbieren der physischen Stärke abgeschnitten, und die gesamte physische Stärke wird nur durch Aufteilen des Monsters verringert. Daher dachte ich, dass sich die Anzahl der Angriffe ändern würde, wenn die physische Stärke H eine Potenz von 2 wäre.
Von hier aus werden wir tatsächlich numerische Berechnungen durchführen und die allgemeine Theorie ableiten.
H Anzahl der Angriffe 1 1 mal 2 ~ 3 3 mal 4 ~ 7 7 mal 8 ~ 15 15 mal Wenn H von 2 n bis 2 n + 1 bis 1 ist, beträgt die Anzahl der Angriffe 2 bis 2 n bis 2 n Sie können sehen, dass es durch die Summe von bis zu ausgedrückt werden kann.
Überlegen Sie nun, ob H zwischen 2 zur n-ten Potenz und 2 zur n + 1-Potenz liegt. Sie wird berechnet, indem eine Dezimalzahl in eine Binärzahl umgewandelt und die Anzahl der Zeichen gezählt wird.
H = int(input())
n = len(bin(H)) - 3
N = [2 ** i for i in range(n + 1)]
print(sum(N))
Wenn H zwischen 2 n 2 und 2 n + 1 -1 liegt, kann die Anzahl der Angriffe als 2 n + 1 -1 ausgedrückt werden. Zusätzlich wurde n erhalten, indem ein Protokoll mit einer Basis von 2 genommen und nach dem Dezimalpunkt abgeschnitten wurde.
import math
H = int(input())
n = math.floor(math.log2(H))
print(2 ** (n + 1) -1)
Anscheinend war es ein berühmtes Problem von Rucksäcken mit begrenzter Anzahl. Ich habe DP (Dynamic Planning Method) überhaupt nicht verstanden und habe dies als Referenz verwendet. Einfach zu verstehen.
https://qiita.com/drken/items/dc53c683d6de8aeacf5a
Erstens ist das Ergebnis, TLE zu werden. (AC für Pypy3) Betrachten Sie die i-te der N Arten von Magie, die Sie verwenden können. Wenn Sie die i-te Magie verwenden können, um die gesamte physische Stärke um j zu reduzieren, ist die erschöpfte magische Kraft dp[j] = dp[j - a] + b Wenn Sie die gesamte physische Stärke um j reduzieren können, ohne die i-te Magie zu verwenden, ist die erschöpfte magische Kraft dp[j] = dp[j] Es wird sein. Vergleichen Sie diese, um den Mindestwert zu ermitteln, und verwenden Sie ihn als dp [j]. Die Anzahl der Elemente von dp [] beträgt H + max (reduzierbare physische Stärke), da die physische Stärke des Monsters perfekt ist und es nicht erforderlich ist, sie zu besiegen. Der Anfangswert ist dp [0] = 0 Da 0 der Mindestwert ist, wird der Fall durch die if-Anweisung geteilt.
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:]))
Ich bedauere, dass die if-Anweisung in der double for-Schleife langsam zu sein scheint und sie verbessert hat, aber es ist TLE. (AC für Pypy3) Da es durch Setzen der Unendlichkeit in das Element von dp [] gemacht wird, ist es nicht notwendig, nach Fall zu urteilen. Es ist leichter zu sehen, aber es dauert länger als die erste Antwort.
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:]))
Ich möchte mit Python AC.
Gingitsune kämpft gegen N Monster. Die Monster sind in einer Reihe aufgereiht und können als auf mehreren geraden Linien liegend betrachtet werden. Das i-te Monster ist an der Koordinate Xi und hat Hi. Gingitsune kann Bomben einsetzen, um Monster anzugreifen. Die Verwendung einer Bombe an der Koordinate x kann die Gesundheit aller Monster im Bereich x - D oder höher und x + D oder niedriger um A verringern. Du kannst die Stärke eines Monsters nur mit einer Bombe reduzieren. Wenn die physische Stärke aller Monster auf 0 oder weniger eingestellt ist, gewinnt der Gingitsune. Finde heraus, wie oft ein Gingitsune mindestens eine Bombe benutzt, um ein Monster zu schlagen.
Die Probe liefert das richtige Ergebnis, aber es war WA. Ordne die Abstände in aufsteigender Reihenfolge an und greife an, bis der kleinste Wert 0 wird. Daher dachte ich, ich würde die physische Stärke der Monster in der Reichweite verringern, die gleichzeitig angegriffen werden, und die Liste neu erstellen.
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