Break through in one and a half minutes. Just write.
H, A = map(int, input().split())
print((H + (A - 1)) // A)
ABC153B - Common Raccoon vs Monster
Break through in two and a half minutes. Just write. Whether the total damage of the special move exceeds the physical strength of the monster, that's it.
H, N = map(int, input().split())
A = list(map(int, input().split()))
if sum(A) >= H:
print('Yes')
else:
print('No')
Break through in two and a half minutes. Just write. I want to defeat the one with as much physical strength as possible with a special move, so just sort and count the first K and subsequent animals as defeated by attack.
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
print(sum(A[K:]))
It breaks through in 7 and a half minutes. Since it is a log, it does not become a TLE, so you can just count it as defined by the recursive function.
from sys import setrecursionlimit
setrecursionlimit(1000000)
H = int(input())
def f(n):
if n == 1:
return 1
else:
return 1 + f(n // 2) * 2
print(f(H))
ABC153E - Crested Ibis vs Monster
Break through in 55 minutes and a half. Brute force with DP.
package main
import (
"bufio"
"fmt"
"math"
"os"
"strconv"
)
func main() {
AMax := 10000
H := readInt()
N := readInt()
AB := make([]struct{ A, B int }, N)
for i := 0; i < N; i++ {
AB[i].A = readInt()
AB[i].B = readInt()
}
dpLen := H + AMax + 1
dp := make([]int, dpLen)
for i := 0; i < dpLen; i++ {
dp[i] = math.MaxInt64
}
dp[0] = 0
for i := 0; i < H; i++ {
if dp[i] == math.MaxInt64 {
continue
}
for j := 0; j < N; j++ {
a := AB[j].A
b := AB[j].B
if dp[i]+b < dp[i+a] {
dp[i+a] = dp[i] + b
}
}
}
result := math.MaxInt64
for i := H; i < dpLen; i++ {
if dp[i] < result {
result = dp[i]
}
}
fmt.Println(result)
}
const (
ioBufferSize = 1 * 1024 * 1024 // 1 MB
)
var stdinScanner = func() *bufio.Scanner {
result := bufio.NewScanner(os.Stdin)
result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
result.Split(bufio.ScanWords)
return result
}()
func readString() string {
stdinScanner.Scan()
return stdinScanner.Text()
}
func readInt() int {
result, err := strconv.Atoi(readString())
if err != nil {
panic(err)
}
return result
}
ABC153F - Silver Fox vs Monster
Lost. I think I would have broken through if the AtCoder Go version was newer and I could sort the slices. If not, I would have rewritten it in C # if I had a little more time left ...
Addendum: Misunderstanding. I didn't understand at all. The key issue was whether the damage to monsters within the range of the bomb could be handled in the order lower than * O * (* N *). Queue the damage and effective range, and if it goes out of range, retire it to implement it with * O * (1) and AC.
from collections import deque
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
q = deque()
t = 0
result = 0
for x, h in XH:
while q:
if x <= q[0][0]:
break
t -= q[0][1]
q.popleft()
h -= t
if h <= 0:
continue
c = (h + A - 1) // A
result += c
t += c * A
q.append((x + 2 * D, c * A))
print(result)
Recommended Posts