[PYTHON] AtCoder Beginner Contest 151 Teilnahmebericht

AtCoder Beginner Contest 151 Teilnahmebericht

ABC151A - Next Alphabet

Brechen Sie in anderthalb Minuten durch. Schreiben Sie einfach.

C = input()

print(chr(ord(C[0]) + 1))

ABC151B - Achieve the Goal

Brechen Sie in 4 Minuten durch. Schreiben Sie einfach.

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

t = sum(A)
if N * M > t + K:
    print(-1)
else:
    print(max(N * M - t, 0))

ABC151C - Count Order

Brechen Sie in 7 ½ Minuten durch. Sie müssen sich nur um die WA nach AC sorgen, die Sie ignorieren müssen.

N, M = map(int, input().split())

ac = [False] * N
wa = [0] * N
for _ in range(M):
    p, S = input().split()
    p = int(p) - 1
    if S == 'AC':
        ac[p] = True
    else:
        if not ac[p]:
            wa[p] += 1

a = 0
b = 0
for i in range(N):
    if ac[i]:
        a += 1
        b += wa[i]
print(*[a, b])

ABC151D - Maze Master

Es brach in 17 Minuten durch. AtCoder Typical Contest 002A - Als ich es sah, erinnerte ich mich an die Suche nach der Breitenpriorität, also suchte ich die Breitenpriorität von allen Stellen aus und löste sie in Richtung des Sammelns der längsten.

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def f(i, j):
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '#' and t[y - 1][x] == -1:
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '#' and t[y + 1][x] == -1:
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '#' and t[y][x - 1] == -1:
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '#' and t[y][x + 1] == -1:
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


result = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            result = max(result, f(i, j))
print(result)

Nachtrag: Es kann sogar mit Worshall Floyd gelöst werden.

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func warshallFloyd(n int, d [][]int) {
	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				d[i][j] = min(d[i][j], d[i][k]+d[k][j])
			}
		}
	}
}

func main() {
	H := readInt()
	W := readInt()

	S := make([]string, H)
	for i := 0; i < H; i++ {
		S[i] = readString()
	}

	n := H * W
	d := make([][]int, n)
	for i := 0; i < n; i++ {
		d[i] = make([]int, n)
		fillInts(d[i], math.MaxInt32)
		d[i][i] = 0
	}

	for y := 0; y < H; y++ {
		for x := 0; x < W; x++ {
			if S[y][x] == '#' {
				continue
			}
			if y-1 >= 0 && S[y-1][x] != '#' {
				d[y*W+x][(y-1)*W+x] = 1
			}
			if y+1 < H && S[y+1][x] != '#' {
				d[y*W+x][(y+1)*W+x] = 1
			}
			if x-1 >= 0 && S[y][x-1] != '#' {
				d[y*W+x][y*W+x-1] = 1
			}
			if x+1 < W && S[y][x+1] != '#' {
				d[y*W+x][y*W+x+1] = 1
			}
		}
	}

	warshallFloyd(n, d)

	result := 0
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if d[i][j] < math.MaxInt32 && d[i][j] > result {
				result = d[i][j]
			}
		}
	}

	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
}

func fillInts(a []int, x int) {
	for i := 0; i < len(a); i++ {
		a[i] = x
	}
}

ABC151E - Max-Min Sums

Ich konnte nicht einmal einen Hinweis bekommen und verlor. 70 Minuten lang musste ich beobachten, wie die Rangliste von den 800ern auf die 1300er abrutschte.

Nachtrag: Ich dachte, es wäre einfach, es in weniger als zwei Monaten zu lösen (lacht).

Beachten Sie zunächst, dass max (X) und min (X) getrennt summiert werden können. Wir können sehen, dass der Minimalwert von max (X) A K </ sub> von sortiertem A ist und der Maximalwert A _{N </ sub> ist. Max (X) ist der Maximalwert A <sub Für die Kombination, die zu> N </ sub> wird, wird ein A N </ sub> bestätigt, und das verbleibende K-1 wird aus dem verbleibenden N-1 ausgewählt, so dass N-1 </ sub> C. K -1 </ sub>, max (X) ist der nächstgrößere Wert, nachdem der Maximalwert A N -1 </ sub> der Maximalwert A N </ sub> ausgewählt wurde Unter der Annahme, dass es so etwas nicht gibt, wird das nächstgrößere A N-1 </ sub> als eins bestätigt und das verbleibende K-1 ausgewählt, so dass N - 2 </ sub> C <-sub> K- 1 </ sub> zählt so bis zum Minimalwert A K </ sub>. Min (X) kann auf die gleiche Weise gelöst werden.}

Wenn Sie fragen (N-1)! Im Voraus können Sie die Kombination mit * O * (log N </ i>) berechnen, also schließlich * O * ( N <) Sie kann mit / i> log N </ i>) berechnet werden.

p = 1000000007

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

fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % p


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], p - 2, p) * pow(fac[k], p - 2, p) % p


A.sort(reverse=True)
result = 0
for i in range(N - K + 1):
    result += A[i] * mcomb(N - (i + 1), K - 1)
    result %= p

A.reverse()
for i in range(N - K + 1):
    result -= A[i] * mcomb(N - (i + 1), K - 1)
    result %= p

print(result)