No.3583 Bipartite Matching Optimization
タグ : / 解いたユーザー数 12
作問者 : 👑
Problem Statement
The time limit for this problem is 6000[ms]. Using a fast language/implementation is recommended.
For reference, the writer's solution runs in 425[ms] in C++ and 5153[ms] in PyPy3.
Problem Statement
You are given $3$ positive integers $N, M, L$ satisfying $L \leq \min \{N,M\}$, an integer sequence $A$ of length $N$, and an integer sequence $B$ of length $M$.
For a permutation $P$ of length $L$ of $\mathbb{N} \cap [1,N] = \{1,\ldots,N\}$ and a permutation $Q$ of length $L$ of $\mathbb{N} \cap [1,M] = \{1,\ldots,M\}$, define
$\displaystyle f(P,Q) = \sum_{k=1}^{L} \left|A_{P_k} - B_{Q_k} \right| $
. Find the minimum value of $f(P,Q)$ over all choices of $P, Q$.
Here, for an integer sequence $a$ and a positive integer $i$ not exceeding its length, $a_i$ denotes the $i$-th element of $a$.
Click here for the definition of a permutation of a specified length
For a set $X$ and a non-negative integer $\ell$, a permutation of length $\ell$ of $X$ is a sequence of length $\ell$ consisting of elements of $X$ whose elements are pairwise distinct.
A permutation of length $\ell$ of $X$ exists if and only if $X$ has at least $\ell$ elements. In particular, since $L \leq \min \{N,M\}$, a permutation $P$ of length $L$ of $\mathbb{N} \cap [1,N] = \{1,\ldots,N\}$ and a permutation $Q$ of length $L$ of $\mathbb{N} \cap [1,M] = \{1,\ldots,M\}$ exist.
For example, the set $\{1,2,3\}$ with $3$ elements has $6$ permutations of length $2$: $(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)$.
Input
The input is given from standard input in $3$ lines in the following format:
- Line $1$ contains $N, M, L$, separated by single-byte spaces.
- Line $2$ contains $A_i$ for each positive integer $i$ not exceeding $N$, in increasing order of $i$, separated by single-byte spaces.
- Line $3$ contains $B_j$ for each positive integer $j$ not exceeding $M$, in increasing order of $j$, separated by single-byte spaces.
$N$ $M$ $L$ $A_1$ $\cdots$ $A_N$ $B_1$ $\cdots$ $B_M$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^3$.
- $M$ is an integer satisfying $1 \leq M \leq 10^3$.
- $L$ is an integer satisfying $1 \leq L \leq \min \{N,M\}$.
- For every positive integer $i$ not exceeding $N$, $A_i$ is an integer satisfying $-10^3 \leq A_i \leq 10^3$.
- For every positive integer $j$ not exceeding $M$, $B_j$ is an integer satisfying $-10^3 \leq B_j \leq 10^3$.
Output
Print the minimum value of $f(P,Q)$ over all choices of $P, Q$ on $1$ line.
Print a newline at the end.
Sample
Sample 1
Input
2 2 1 1 0 0 -1
Output
0
For example, when $P = (2), Q = (1)$,
$\displaystyle f(P,Q) = \left| A_{P_1} - B_{Q_1} \right| = |0 - 0| = 0 $
holds. The value of $f(P,Q)$ is never less than $0$.
Sample 2
Input
3 2 2 0 2 4 5 1
Output
2
For example, when $P = (3,1), Q = (1,2)$,
$\displaystyle f(P,Q) = \left| A_{P_1} - B_{Q_1} \right| + \left| A_{P_2} - B_{Q_2} \right| = |4 - 5| + |0 - 1| = 2 $
holds. The value of $f(P,Q)$ is never less than $2$.
Sample 3
Input
3 3 3 0 0 0 1 1 1
Output
3
No matter how $P, Q$ are chosen,
$\displaystyle f(P,Q) = \left| A_{P_1} - B_{Q_1} \right| + \left| A_{P_2} - B_{Q_2} \right| + \left| A_{P_3} - B_{Q_3} \right| = |0 - 1| + |0 - 1| + |0 - 1| = 3 $
holds.
Sample 4
Input
5 5 1 2 5 5 12 13 0 3 9 9 18
Output
1
For example, when $P = (1), Q = (2)$,
$\displaystyle f(P,Q) = \left| A_{P_1} - B_{Q_1} \right| = |2 - 3| = 1 $
holds. The value of $f(P,Q)$ is never less than $1$.
Sample 5
Input
5 5 2 2 5 5 12 13 0 3 9 9 18
Output
4
This is the same as Sample 4 except for $L$. For example, when $P = (1,2), Q = (1,2)$,
$\displaystyle f(P,Q) = \left| A_{P_1} - B_{Q_1} \right| + \left| A_{P_2} - B_{Q_2} \right| = |2 - 0| + |5 - 3| = 4 $
holds. The value of $f(P,Q)$ is never less than $4$.
Sample 6
Input
5 5 4 2 5 5 12 13 0 3 9 9 18
Output
11
This is the same as Sample 5 except for $L$. For example, when $P = (1,2,4,5), Q = (1,2,3,4)$,
$\displaystyle f(P,Q) = \left| A_{P_1} - B_{Q_1} \right| + \left| A_{P_2} - B_{Q_2} \right| + \left| A_{P_3} - B_{Q_3} \right| + \left| A_{P_4} - B_{Q_4} \right| = |2 - 0| + |5 - 3| + |12 - 9| + |13 - 9| = 11 $
holds. The value of $f(P,Q)$ is never less than $11$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。