Break through in one and a half minutes. Just write.
C = input()
print(chr(ord(C[0]) + 1))
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))
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])
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
}
}
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>).
Note that Python always results in a positive integer, but in some languages it can be a negative integer, in which case you need to revert to a positive integer.
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)
Recommended Posts