Percer en une minute et demie. Il suffit d'écrire.
C = input()
print(chr(ord(C[0]) + 1))
Percer en 4 minutes. Il suffit d'écrire.
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))
Percer en 7 minutes et demie. Vous n'avez qu'à vous soucier de la WA après AC que vous devez ignorer.
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])
Il a éclaté en 17 minutes Concours AtCoder Typique 002A - Au moment où je l'ai vu, je me suis souvenu de la recherche de priorité de largeur, donc j'ai cherché la priorité de largeur de tous les endroits et l'ai résolue dans le sens de la collecte la plus longue.
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)
Post-scriptum: il peut être résolu même avec 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
}
}
Je n'ai même pas pu me faire une idée et j'ai perdu ... Pendant 70 minutes, j'ai fini par regarder le classement descendre des 800 aux 1300.
Post-scriptum: Je pensais que ce serait facile à résoudre en moins de deux mois (rires).
Tout d'abord, notez que max (X) et min (X) peuvent être additionnés séparément. Nous pouvons voir que la valeur minimale de max (X) est A K </ sub> de A trié et la valeur maximale est A N </ sub>. Max (X) est la valeur maximale A <sub. Pour la combinaison qui devient> N </ sub>, un A N </ sub> est confirmé, et le K-1 restant est sélectionné parmi les N-1 restants donc N-1 </ sub> C K -1 </ sub>, max (X) est le plus grand suivant après la valeur maximale A N -1 </ sub> est la valeur maximale A N </ sub> est sélectionné En supposant que cela n'existe pas, le prochain plus grand A N-1 </ sub> est confirmé comme un, et le K-1 restant est sélectionné, donc N --2 </ sub> C K- 1 </ sub>, vous pouvez compter jusqu'à la valeur minimale A K </ sub> comme ça. Vous pouvez résoudre min (X) de la même manière.
Si vous demandez (N-1)! À l'avance, vous pouvez calculer la combinaison avec * O * (log N </ i>), donc finalement * O * ( N < Il peut être calculé avec / i> log N </ i>).
Notez que Python donne toujours un entier positif, mais dans certains langages, il peut s'agir d'un entier négatif, auquel cas vous devez revenir à un entier positif.
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