概要

この問題は、与えられた \(N\) 人の配達員（体力 \(A_i\)）を \(M\) 件の配達依頼（必要体力 \(B_j\)）に割り当てる問題です。 満たすべき条件は、すべての依頼に対して「配達員の体力 \(\ge\) 必要体力」となる割り当てが存在すること（第一目標）であり、その中で「配達員の体力 \(=\) 必要体力」となる「ぴったり」のペア数を最大化すること（第二目標）です。

ソートと貪欲法、および2ポインタ（Two Pointers）を用いることで、効率的に解くことができます。

---

考察

1. 第一目標：すべての依頼に割り当て可能か？

すべての依頼をこなすためには、配達員の中から \(M\) 人を選ぶ必要があります。 「割り当てが可能か」を判定する上で、最も有利な選び方は「体力が高い上位 \(M\) 人の配達員を、必要体力が低い依頼から順に割り当てる」ことです。

具体的には、配達員の体力 \(A\) と依頼の必要体力 \(B\) をそれぞれ昇順にソートします。 このとき、体力の上位 \(M\) 人は \(A\) の後ろから \(M\) 個、すなわち \(A[N-M], A[N-M+1], \dots, A[N-1]\) となります。 これらを、ソートされた依頼 \(B[0], B[1], \dots, B[M-1]\) に順番に対応させます。

すべての \(0 \le i < M\) について、以下の条件が成り立つかを確認します。 $\(A[N - M + i] \ge B[i]\)$

もしこの条件を1つでも満たさない \(i\) が存在する場合、どのように配達員を選んでも全員を割り当てることは不可能です。したがって、この場合は -1 を出力します。

2. 第二目標：ぴったりの割り当ての最大化

第一目標が達成可能であると判定された場合、次に「ぴったり（\(A_i = B_j\)）」の割り当て数を最大化します。

一見すると、「ぴったり」のペアを増やすことで、他の依頼に割り当てる配達員の体力が足りなくなり、第一目標が達成できなくなる（全体の割り当てが破綻する）のではないかと心配になるかもしれません。 しかし、実は「第一目標が達成可能であるならば、ぴったりのペアを貪欲に最大化しても、残りのメンバーで第一目標を必ず達成できる」という性質があります。

なぜなら、ある値 \(v\) について \(A_i = B_j = v\) というペアを作って取り除くことは、全体の割り当てにおいて「体力 \(v\) の配達員」と「必要体力 \(v\) の依頼」を相殺することに相当するからです。体力 \(v\) の配達員は必要体力 \(v\) 以下の依頼しかこなせず、必要体力 \(v\) の依頼は体力 \(v\) 以上の配達員しかこなせないため、これらを1対1でペアにして除外しても、残りの要素の間での「割り当て可能性」に悪影響を与えません。

したがって、第二目標の最大値は、各値 \(v\) について以下の総和を求めるだけで得られます。 $\(\sum_{v} \min(\text{Aにおける } v \text{ の個数}, \text{Bにおける } v \text{ の個数})\)$

---

アルゴリズム

\(A\) と \(B\) がすでに昇順にソートされているため、2ポインタ（Two Pointers）を用いることで、共通する要素の個数を \(O(N + M)\) で効率的に数え上げることができます。

1. 配列 \(A\) と \(B\) を昇順にソートします。
2. 第一目標が達成可能か判定します。
   • すべての \(0 \le i < M\) について \(A[N - M + i] \ge B[i]\) であるかを確認し、満たさなければ -1 を出力して終了します。
3. 2つのポインタ \(i\)（\(A\) 用）と \(j\)（\(B\) 用）を \(0\) に初期化します。
4. \(i < N\) かつ \(j < M\) である限り、以下を繰り返します。
   • \(A[i] < B[j]\) の場合：\(A[i]\) は \(B[j]\) 以降のどの依頼にもぴったりになり得ないため、 \(i\) を進めます（\(i \leftarrow i + 1\)）。
   • \(A[i] > B[j]\) の場合：\(B[j]\) は \(A[i]\) 以降のどの配達員にもぴったりになり得ないため、 \(j\) を進めます（\(j \leftarrow j + 1\)）。
   • \(A[i] == B[j]\) の場合：
     • その共通の値を \(val\) とします。
     • \(A\) において値が \(val\) である要素の個数 \(countA\) をカウントし、ポインタ \(i\) を進めます。
     • \(B\) において値が \(val\) である要素の個数 \(countB\) をカウントし、ポインタ \(j\) を進めます。
     • 答えのカウントに \(\min(countA, countB)\) を加算します。

---

計算量

• 時間計算量: \(O(N \log N + M \log M)\)

  • 配列 \(A, B\) のソートに \(O(N \log N + M \log M)\) かかります。
  • 第一目標の判定に \(O(M)\)、第二目標の2ポインタによる走査に \(O(N + M)\) かかります。
  • 全体としてソートがボトルネックとなり、全体の計算量は \(O(N \log N + M \log M)\) です。これは \(N, M \le 2 \times 10^5\) の制約下で十分高速に動作します。

• 空間計算量: \(O(N + M)\)

  • 入力された配列 \(A\) と \(B\) を保持するためのメモリ空間が必要です。

---

実装のポイント

• 2ポインタの境界条件: 同じ値をカウントする while ループの中で、インデックス \(i, j\) がそれぞれ配列のサイズ \(N, M\) を超えないように i < N や j < M の条件を必ず含める必要があります。

• 高速な入出力: C++では入力データのサイズが大きいため、std::cin の高速化（ios_base::sync_with_stdio(false); cin.tie(NULL);）を行うことで、入出力による実行時間超過（TLE）を防ぎます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector<long long> B(M);
    for (int i = 0; i < M; ++i) {
        cin >> B[i];
    }

    // 昇順にソート
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    // 第一目標の判定：
    // B の各要素 B[i] に対して、A の大きい方から M 個を順に対応させたときに、
    // すべての i について A[N - M + i] >= B[i] が成り立つかを確認する。
    bool possible = true;
    for (int i = 0; i < M; ++i) {
        if (A[N - M + i] < B[i]) {
            possible = false;
            break;
        }
    }

    if (!possible) {
        cout << -1 << "\n";
        return 0;
    }

    // 第二目標の計算：
    // 第一目標が達成可能な場合、A_i = B_j となるペアの最大数は、
    // 各値 v について min(Aにおけるvの個数, Bにおけるvの個数) の総和に等しい。
    // ソート済みなので、two pointers を用いて O(N + M) で計算できる。
    long long ans = 0;
    int i = 0, j = 0;
    while (i < N && j < M) {
        if (A[i] < B[j]) {
            i++;
        } else if (A[i] > B[j]) {
            j++;
        } else {
            long long val = A[i];
            long long countA = 0;
            while (i < N && A[i] == val) {
                countA++;
                i++;
            }
            long long countB = 0;
            while (j < M && B[j] == val) {
                countB++;
                j++;
            }
            ans += min(countA, countB);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。