解説 - AtCoder Weekday Contest 0032 Beta

公式

D - アルバイトのシフト割り当て / Part-Time Job Shift Assignment 解説 by kyopro_friends

$A$, $D$ ともに降順にソートされているとしてよいです。

$\sum_{j=1}^{M}(A_{f(k)}-D_j)=\sum_{j=1}^{M}A_{f(k)} - \sum_{j=1}^{M}D_j$ であり、第 2 項は定数なので、第 1 項を最大化すればよいです。

$A_{f(j)}\geq D_j$ の条件を無視すれば、第 1 項は $A_1+A_2+\ldots+A_M$ が最大値となります。実は、条件を満たす割り当てが存在しない場合を除き、常に $f(i)=i$ とする割り当て方が可能です。

証明

「$f(i)=i$ という割り当てが条件を満たさないならば、条件を満たす割り当ては存在しない」を示します。この割り当てが条件を満たさないときある $i$ で $A_i < D_i$ となります。そのような最小の $i$ をとると、要求スキル値が $D_i$ 以上の業務が $i$ 個以上存在するにも関わらず、スキル値が $D_i$ 以上のアルバイトが $i$ 人未満しかいないため、条件を満たす割り当ては存在しません。

よって求める答えは、全ての $1 \leq i \leq M$ で $A_i \geq D_i$ のとき $(A_1+A_2+\dots+A_M)-(D_1+D_2+\dots+D_M)$ 、そうでないとき $-1$ です。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<int>a(n),d(m);
  for(int i=0; i<n; i++) cin >> a[i];
  for(int i=0; i<m; i++) cin >> d[i];
  sort(a.rbegin(), a.rend());
  sort(d.rbegin(), d.rend());

  long long ans=0;
  for(int i=0; i<m; i++){
    if(a[i] < d[i]){
      cout << -1 << endl;
      return 0;
    }
    ans += a[i] - d[i];
  }
  cout << ans << endl;
}

実装例 (Python)

N, M = map(int, input().split())
A = list(map(int, input().split()))
D = list(map(int, input().split()))
A.sort(reverse=True)
D.sort(reverse=True)

ans = 0
for i in range(M):
  if A[i] < D[i]:
    print(-1)
    exit()
  ans += A[i] - D[i]

print(ans)