It seems that the score when a i </ sub> is sorted in descending order and b i </ sub> is sorted in ascending order is always the maximum value, but the same maximum value is used. If there are more than one, I can't think of a way to solve how many. If you think about it carefully, N ≤ 9 and 9! ≒ 3.6 × 10 5 </ sup>, so I was able to try all of them.
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)])
The probability is the number of N × M combinations that exceed C divided by N × M. If b is sorted, the combination with a i </ sub> exceeds C. The number of i </ sub> can be calculated by * O * (log M </ i>), so * O * ((* N * + * M *) log M </ i>) and can be solved. You may sort a.
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))
Since it is a chance to get a big score later, it seems that the maximum value is to put out a in ascending order. It is difficult to find the number of sheets smaller than a i </ sub> from the accumulated b If you want to use, you have to keep the sort, and every time you sort naive, it becomes * O * (* N * 2 </ sup> log N </ i>) If you divide the array into two, small and large, and sort only the smaller one each time, you can AC by reducing the amount of calculation.
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)
Postscript: It seems that the assumed solution was coordinate compression + BIT, so I still solved it.
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)
You don't have to pay a one-time toll. I did a breadth-first search by dividing the DP table before and after using the right. I didn't need the Dijkstra method. If I set the initial value to math.MaxInt64, it overflowed. I died and made math.MaxInt32, but this time it was too small to WA and settled on 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