Lorsqu'un i </ sub> est trié par ordre décroissant et b i </ sub> est trié par ordre croissant, le score est toujours le maximum, mais le même maximum est Je n'arrive pas à trouver un moyen de résoudre le nombre lorsqu'il y en a plusieurs. Si vous y réfléchissez bien, N ≤ 9 et 9! ≒ 3,6 × 10 5 </ sup>, j'ai donc pu tous les essayer.
from itertools import permutations
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d = {}
for x in permutations(a):
t = 0
for i in range(N):
t += max(x[i] - b[i], 0)
d.setdefault(t, 0)
d[t] += 1
print(d[max(d)])
La probabilité est le nombre de N × M combinaisons qui dépassent C divisé par N × M. Si b est trié, la combinaison avec a i </ sub> dépasse C b Le nombre de i </ sub> peut être calculé par * O * (log M </ i>), donc * O * ((* N * + * M *) log M </ i>) et peut être résolu. Vous pouvez trier un fichier.
from bisect import bisect_left
N, M, C = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.sort()
c = 0
for x in a:
t = ((C + 1) + x - 1) // x
c += M - bisect_left(b, t)
print(c / (N * M))
Puisqu'il s'agit d'une chance d'obtenir un gros score plus tard, il semble que la valeur maximale soit de mettre a dans l'ordre croissant. Il est difficile de trouver le nombre de feuilles inférieur à a i </ sub> à partir du b accumulé Si vous voulez utiliser, vous devez garder le tri, et si vous triez naïf à chaque fois, ce sera * O * (* N * 2 </ sup> log N </ i>) et bien sûr TLE. Vous pouvez AC en divisant le tableau en deux, petit et grand, et en ne triant que le plus petit à chaque fois et en réduisant la quantité de calcul.
from bisect import bisect_left
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
t0 = []
t1 = []
result = 0
for i in range(N):
result += bisect_left(t0, a[i])
t1.append(b[i])
t1.sort()
result += bisect_left(t1, a[i])
if len(t1) == 300:
t0.extend(t1)
t0.sort()
t1.clear()
print(result)
Post-scriptum: Il semble que la solution supposée était la compression de coordonnées + BIT, donc je l'ai toujours résolue.
def bit_add(bit, i, x):
i += 1
n = len(bit)
while i <= n:
bit[i - 1] += x
i += i & -i
def bit_sum(bit, i):
result = 0
i += 1
while i > 0:
result += bit[i - 1]
i -= i & -i
return result
def bit_query(bit, start, stop):
if start == 0:
return bit_sum(bit, stop - 1)
else:
return bit_sum(bit, stop - 1) - bit_sum(bit, start - 1)
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
t = {j: i for i, j in enumerate(sorted(set(a + b)))}
bit = [0] * len(t)
a.sort()
result = 0
for i in range(N):
bit_add(bit, t[b[i]], 1)
result += bit_query(bit, 0, t[a[i]])
print(result)
Vous n'avez pas à payer de péage unique. La table DP avant et après l'utilisation de la droite a été divisée en recherche de priorité de largeur et AC a été effectuée. La méthode Dikstra n'était pas nécessaire. Si la valeur initiale est définie sur «math.MaxInt64», elle déborde. Quand je suis mort et que j'ai fait math.MaxInt32, c'était trop petit cette fois et je me suis arrêté sur math.MaxInt64 >> 1.
package main
import (
"bufio"
"fmt"
"math"
"os"
"strconv"
)
func min(x, y int) int {
if x < y {
return x
}
return y
}
func main() {
defer flush()
N := readInt()
M := readInt()
c := make([][]int, N)
for i := 0; i < N; i++ {
c[i] = make([]int, N)
}
for i := 0; i < M; i++ {
h := readInt() - 1
w := readInt() - 1
c[h][w] = readInt()
}
dpa := make([][]int, N)
dpb := make([][]int, N)
for i := 0; i < N; i++ {
dpa[i] = make([]int, N)
dpb[i] = make([]int, N)
for j := 0; j < N; j++ {
dpa[i][j] = math.MaxInt64 >> 1
dpb[i][j] = math.MaxInt64 >> 1
}
}
dpa[0][0] = 0
q := make([][3]int, 0)
q = append(q, [3]int{0, 0, 0})
for len(q) != 0 {
y := q[0][0]
x := q[0][1]
t := q[0][2]
q = q[1:]
if t == 0 {
if y != 0 {
if dpa[y-1][x] > dpa[y][x]+1+c[y-1][x] {
dpa[y-1][x] = dpa[y][x] + 1 + c[y-1][x]
q = append(q, [3]int{y - 1, x, 0})
}
if c[y-1][x] > 0 {
if dpb[y-1][x] > dpa[y][x]+1 {
dpb[y-1][x] = dpa[y][x] + 1
q = append(q, [3]int{y - 1, x, 1})
}
}
}
if y != N-1 {
if dpa[y+1][x] > dpa[y][x]+1+c[y+1][x] {
dpa[y+1][x] = dpa[y][x] + 1 + c[y+1][x]
q = append(q, [3]int{y + 1, x, 0})
}
if c[y+1][x] > 0 {
if dpb[y+1][x] > dpa[y][x]+1 {
dpb[y+1][x] = dpa[y][x] + 1
q = append(q, [3]int{y + 1, x, 1})
}
}
}
if x != 0 {
if dpa[y][x-1] > dpa[y][x]+1+c[y][x-1] {
dpa[y][x-1] = dpa[y][x] + 1 + c[y][x-1]
q = append(q, [3]int{y, x - 1, 0})
}
if c[y][x-1] > 0 {
if dpb[y][x-1] > dpa[y][x]+1 {
dpb[y][x-1] = dpa[y][x] + 1
q = append(q, [3]int{y, x - 1, 1})
}
}
}
if x != N-1 {
if dpa[y][x+1] > dpa[y][x]+1+c[y][x+1] {
dpa[y][x+1] = dpa[y][x] + 1 + c[y][x+1]
q = append(q, [3]int{y, x + 1, 0})
}
if c[y][x+1] > 0 {
if dpb[y][x+1] > dpa[y][x]+1 {
dpb[y][x+1] = dpa[y][x] + 1
q = append(q, [3]int{y, x + 1, 1})
}
}
}
} else {
if y != 0 {
if dpb[y-1][x] > dpb[y][x]+1+c[y-1][x] {
dpb[y-1][x] = dpb[y][x] + 1 + c[y-1][x]
q = append(q, [3]int{y - 1, x, 1})
}
}
if y != N-1 {
if dpb[y+1][x] > dpb[y][x]+1+c[y+1][x] {
dpb[y+1][x] = dpb[y][x] + 1 + c[y+1][x]
q = append(q, [3]int{y + 1, x, 1})
}
}
if x != 0 {
if dpb[y][x-1] > dpb[y][x]+1+c[y][x-1] {
dpb[y][x-1] = dpb[y][x] + 1 + c[y][x-1]
q = append(q, [3]int{y, x - 1, 1})
}
}
if x != N-1 {
if dpb[y][x+1] > dpb[y][x]+1+c[y][x+1] {
dpb[y][x+1] = dpb[y][x] + 1 + c[y][x+1]
q = append(q, [3]int{y, x + 1, 1})
}
}
}
}
println(min(dpa[N-1][N-1], dpb[N-1][N-1]))
}
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
}
var stdoutWriter = bufio.NewWriter(os.Stdout)
func flush() {
stdoutWriter.Flush()
}
func println(args ...interface{}) (int, error) {
return fmt.Fprintln(stdoutWriter, args...)
}
Recommended Posts