No.3583 二部マッチング最適化
p-adic問題文
この問題の実行時間制限は6000[ms]です。高速な言語・処理系の使用をおすすめします。
参考までに、writer解の実行時間はc++で425[ms]、PyPy3で5153[ms]です。
問題文
$L \leq \min \{N,M\}$ を満たす $3$ 個の正整数 $N, M, L$ と長さ $N$ の整数列 $A$ と 長さ $M$ の整数列 $B$ が与えられます。
$\mathbb{N} \cap [1,N] = \{1,\ldots,N\}$ の長さ $L$ の順列 $P$ と $\mathbb{N} \cap [1,M] = \{1,\ldots,M\}$ の長さ $L$ の順列 $Q$ に対し、
$\displaystyle f(P,Q) = \sum_{k=1}^{L} \left|A_{P_k} - B_{Q_k} \right| $
と定めます。$P, Q$ を動かした時の $f(P,Q)$ の最小値を求めてください。
ただし整数列 $a$ とその長さ以下の正整数 $i$ に対し、$a_i$ で $a$ の $i$ 個目の成分を表します。
長さの指定された順列の定義はこちら（クリックで開く）
集合 $X$ と非負整数 $\ell$ に対し、$X$ の長さ $\ell$ の順列とは、$X$ の要素からなる長さ $\ell$ の列であって各成分が相異なるもののことです。
$X$ の長さ $\ell$ の順列が存在する必要十分条件は $X$ が $\ell$ 個以上の要素を持つことであり、特に $L \leq \min \{N,M\}$ より $\mathbb{N} \cap [1,N] = \{1,\ldots,N\}$ の長さ $L$ の順列 $P$ や $\mathbb{N} \cap [1,M] = \{1,\ldots,M\}$ の長さ $L$ の順列 $Q$ は存在します。
例えば要素数 $3$ の集合 $\{1,2,3\}$ の長さ $2$ の順列は $(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)$ の $6$ 通りあります。
入力
入力は標準入力を用いて以下の形式で $3$ 行で与えられます：
- $1$ 行目に $N, M, L$ が半角空白区切りで与えられます。
- $2$ 行目に $N$ 以下の各正整数 $i$ に対する $A_i$ が $i$ の小さい順に半角空白区切りで与えられます。
- $3$ 行目に $M$ 以下の各正整数 $j$ に対する $B_j$ が $j$ の小さい順に半角空白区切りで与えられます。
$N$ $M$ $L$ $A_1$ $\cdots$ $A_N$ $B_1$ $\cdots$ $B_M$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^3$ を満たす整数である。
- $M$ は $1 \leq M \leq 10^3$ を満たす整数である。
- $L$ は $1 \leq L \leq \min \{N,M\}$ を満たす整数である。
- $N$ 以下の任意の正整数 $i$ に対し、$A_i$ は $-10^3 \leq A_i \leq 10^3$ を満たす整数である。
- $M$ 以下の任意の正整数 $j$ に対し、$B_j$ は $-10^3 \leq B_j \leq 10^3$ を満たす整数である。
出力
$P, Q$ を動かした時の $f(P,Q)$ の最小値を$1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 2 1 1 0 0 -1
出力
0
例えば $P = (2), Q = (1)$ の時
$\displaystyle f(P,Q) = \left| A_{P_1} - B_{Q_1} \right| = |0 - 0| = 0 $
となります。$f(P,Q)$ の値が $0$ を下回ることはありません。
サンプル2
入力
3 2 2 0 2 4 5 1
出力
2
例えば $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 $
となります。$f(P,Q)$ の値が $2$ を下回ることはありません。
サンプル3
入力
3 3 3 0 0 0 1 1 1
出力
3
$P, Q$ をどのように選んでも
$\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 $
となります。
サンプル4
入力
5 5 1 2 5 5 12 13 0 3 9 9 18
出力
1
例えば $P = (1), Q = (2)$ の時
$\displaystyle f(P,Q) = \left| A_{P_1} - B_{Q_1} \right| = |2 - 3| = 1 $
となります。$f(P,Q)$ の値が $1$ を下回ることはありません。
サンプル5
入力
5 5 2 2 5 5 12 13 0 3 9 9 18
出力
4
$L$ 以外サンプル4と同じです。例えば $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 $
となります。$f(P,Q)$ の値が $4$ を下回ることはありません。
サンプル6
入力
5 5 4 2 5 5 12 13 0 3 9 9 18
出力
11
$L$ 以外サンプル5と同じです。例えば $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 $
となります。$f(P,Q)$ の値が $11$ を下回ることはありません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。