問題一覧 > 教育的問題

No.3583 Bipartite Matching Optimization

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : 👑 p-adic
お気に入りにしたユーザー ProblemId : 12418 / 自分の提出
問題文最終更新日: 2026-06-28 14:58:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 503 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。