[PYTHON] AtCoder Beginner Contest 153 Rapport de participation

AtCoder Beginner Contest 153 Rapport de participation

ABC153A - Serval vs Monster

Percer en une minute et demie. Il suffit d'écrire.

H, A = map(int, input().split())

print((H + (A - 1)) // A)

ABC153B - Common Raccoon vs Monster

Percer dans deux minutes et demie. Il suffit d'écrire. Si le total des dégâts du coup spécial dépasse la force physique du monstre, c'est tout.

H, N = map(int, input().split())
A = list(map(int, input().split()))

if sum(A) >= H:
    print('Yes')
else:
    print('No')

ABC153C - Fennec vs Monster

Percer dans deux minutes et demie. Il suffit d'écrire. Je veux vaincre celui qui a le plus de force physique possible avec un coup spécial, alors il suffit de trier et de compter le premier K et les animaux suivants comme vaincus par une attaque.

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)
print(sum(A[K:]))

ABC153D - Caracal vs Monster

Il passe en 7 minutes et demie. Comme il s'agit d'un journal, il ne devient pas un TLE, il suffit donc de le compter comme défini par la fonction récursive.

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

Brisez en 55 minutes et demie. Tournoi à la ronde avec 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

Perdu. Je pense que j'aurais percé si la version Go d'AtCoder était plus récente et que je pouvais trier les tranches. Sinon, je l'aurais réécrite en C # s'il me restait un peu plus de temps ...

Addendum: Malentendu. Je n'ai pas compris du tout. La question clé était de savoir si les dégâts infligés aux monstres à portée de la bombe pouvaient être traités dans un ordre inférieur à * O * (* N *). Mettez en file d'attente les dégâts et la portée effective, et s'il est hors de portée, retirez-le et implémentez-le avec * O * (1).

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)