[PYTHON] AtCoder Beginner Contest 153 Teilnahmebericht

AtCoder Beginner Contest 153 Teilnahmebericht

ABC153A - Serval vs Monster

Brechen Sie in anderthalb Minuten durch. Schreiben Sie einfach.

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

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

ABC153B - Common Raccoon vs Monster

Brechen Sie in zweieinhalb Minuten durch. Schreiben Sie einfach. Ob der Gesamtschaden des Spezialzugs die physische Stärke des Monsters übersteigt, das war's.

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

Brechen Sie in zweieinhalb Minuten durch. Schreiben Sie einfach. Ich möchte den einen mit so viel körperlicher Kraft wie möglich mit einem Spezialzug besiegen. Sortieren und zählen Sie also einfach das erste K und die nachfolgenden Tiere, die durch einen Angriff besiegt wurden.

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

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

ABC153D - Caracal vs Monster

Es bricht in 7 ½ Minuten durch. Da es sich um ein Protokoll handelt, wird es nicht zu einem TLE. Es ist also in Ordnung, nur so zu zählen, wie es durch die rekursive Funktion definiert ist.

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

In 55 Minuten durchbrechen. Round-Robin mit 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

Ich glaube, ich wäre durchgebrochen, wenn die Go-Version von AtCoder neuer gewesen wäre und ich die Slices sortieren könnte. Wenn nicht, hätte ich sie in C # umgeschrieben, wenn ich noch etwas Zeit gehabt hätte ...

Nachtrag: Missverständnis. Ich habe es überhaupt nicht verstanden. Die Hauptfrage war, ob der Schaden an Monstern in Reichweite der Bombe in einer Reihenfolge behandelt werden kann, die unter * O * (* N *) liegt. Stellt den Schaden und die effektive Reichweite in die Warteschlange. Wenn er außerhalb der Reichweite liegt, ziehen Sie ihn zurück und implementieren Sie ihn mit * 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)