AtCoder Beginner Contest 151 Participation Report

AtCoder Beginner Contest 151 Participation Report

ABC151A - Next Alphabet

Break through in one and a half minutes. Just write.

C = input()

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

ABC151B - Achieve the Goal

Break through in 4 minutes. Just write.

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

Break through in 7 and a half minutes. You only have to worry about the WA after AC that you have to ignore.

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

It broke through in 17 minutes. AtCoder Typical Contest 002A --The moment I saw it, I remembered the breadth-first search, so I searched all the places and solved it in the direction of collecting the longest.

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)

Postscript: It can be solved even with Worshall Floyd.

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

I couldn't even get a clue and lost. For 70 minutes, I ended up watching the rankings slide down from the 800s to the 1300s.

Postscript: I thought it would be easy to solve in less than two months (laughs).

First, note that max (X) and min (X) can be summed separately. We can see that the minimum value of max (X) is A _{K </ sub> of sorted A and the maximum value is A N </ sub>. Max (X) is the maximum value A <sub. For the combination that becomes> N </ sub>, one A N </ sub> is confirmed, and the remaining K-1 is selected from the remaining N-1 so N-1 </ sub> C The maximum value A N </ sub> is selected for the combination in which K-1 </ sub> and max (X) are the next largest A N-1 </ sub> after the maximum value. Assuming that there is no such thing, the next largest A N-1 </ sub> is confirmed as one, and the remaining K-1 is selected, so N --2 </ sub> C K- 1 </ sub>, you can count up to the minimum value A K </ sub> like that. You can solve min (X) in the same way.}

The combination can be calculated with * O * (log N </ i>) if you ask for (N-1)! In advance, so finally * O * ( N < It can be calculated with / i> log N </ i>).

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)