# yukicoder contest 273 Participation record

A 1279 Array Battle

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)])
``````

B 1280 Beyond C

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))
``````

D 1282 Display Elements

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):
result += bit_query(bit, 0, t[a[i]])
print(result)
``````

E 1283 Extra Fee

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()

c := make([][]int, N)
for i := 0; i < N; i++ {
c[i] = make([]int, N)
}

for i := 0; i < M; i++ {
}

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
}()

stdinScanner.Scan()
return stdinScanner.Text()
}

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...)
}
``````