概要

この問題は、与えられた配達員の体力値 \(A\) と配達依頼の必要体力値 \(B\) に対して、すべての依頼をこなせるか判定し（第一目標）、可能な場合は体力値が完全に一致する「ぴったりの割り当て」の数を最大化する（第二目標）問題です。

配列をソートした上で、貪欲法による第一目標の判定と、2ポインタ（尺取り法）による第二目標の最適化を行うことで、効率的に解くことができます。

---

考察

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

\(M\) 件の依頼をすべてこなすためには、当然ながら体力が高い上位 \(M\) 人の配達員を割り当てるのが最も有利です。

そこで、配達員の体力 \(A\) と依頼の必要体力 \(B\) をそれぞれ昇順（小さい順）にソートします。 体力が高い上位 \(M\) 人の配達員を \(A' = [A_{N-M}, A_{N-M+1}, \ldots, A_{N-1}]\) としたとき、すべての \(i\) (\(0 \leq i < M\)) について以下が成り立つ必要があります。 $\(A_{N-M+i} \geq B_i\)\( もしこの条件を1つでも満たさない \)i$ がある場合、どのように配達員を選んでも全員を割り当てることは不可能です。この場合は -1 を出力して終了します。

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

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

一見すると、「ぴったりペアを優先して作ると、他の依頼に体力の高い配達員を回せなくなり、第一目標が達成できなくなるのでは？」と心配になるかもしれません。しかし、実は「第一目標が達成可能であるならば、ぴったりペアを最大化しても、第一目標を達成する割り当てが必ず存在する」という性質があります。

なぜ単に共通要素の個数を数えるだけで良いのか？

例えば、ある有効な割り当てにおいて、ぴったりにできるはずの \(A_i = B_j\) がペアになっておらず、別の割り当てになっているとします。 - 配達員 \(i\)（体力 \(A_i\)）が 依頼 \(k\)（必要体力 \(B_k\)）に割り当てられている（\(A_i \geq B_k\)） - 配達員 \(l\)（体力 \(A_l\)）が 依頼 \(j\)（必要体力 \(B_j\)）に割り当てられている（\(A_l \geq B_j\)）

ここで \(A_i = B_j\) となるペアを作りたいです。もし割り当てを入れ替えて \((A_i, B_j)\) と \((A_l, B_k)\) にしたとします。 - \((A_i, B_j)\) は \(A_i = B_j\) なので、当然体力条件を満たします（ぴったりペア）。 - \((A_l, B_k)\) については、\(A_l \geq B_j = A_i \geq B_k\) より \(A_l \geq B_k\) が成り立つため、こちらも体力条件を満たします。

このように、条件を満たす割り当てが存在するならば、割り当ての整合性を保ったまま、作れるぴったりペアをすべて作ることができます。 したがって、この問題の第二目標は、単に「マルチセット（重複を許す集合）としての \(A\) と \(B\) の共通要素の最大数」を求める問題に帰着されます。

---

アルゴリズム

1. ソート: 配達員の体力配列 \(A\) と、依頼の必要体力配列 \(B\) をそれぞれ昇順にソートします。

2. 第一目標の判定: \(A\) の末尾 \(M\) 個の要素と \(B\) の \(M\) 個の要素を順番に比較します。 すべての \(0 \leq i < M\) について \(A[N - M + i] \geq B[i]\) が成り立っているか確認し、満たさなければ -1 を出力します。

3. 第二目標の計算（2ポインタ）: ソート済みの \(A\) と \(B\) に対して、2つのポインタ ptr_a, ptr_b を用いて共通要素の個数をカウントします。

   • \(A[\text{ptr\_a}] == B[\text{ptr\_b}]\) の場合：共通要素が見つかったので、カウントを \(1\) 増やし、両方のポインタを進めます。
   • \(A[\text{ptr\_a}] < B[\text{ptr\_b}]\) の場合：\(A\) の値が小さすぎるため、ptr_a を進めます。
   • \(A[\text{ptr\_a}] > B[\text{ptr\_b}]\) の場合：\(B\) の値が小さすぎるため、ptr_b を進めます。

---

計算量

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

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

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

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

---

実装のポイント

• 1-indexed と 0-indexed の違い: Pythonのリストは 0-indexed であるため、第一目標の判定で \(A\) の比較対象となるインデックスは N - M + i となります。

• 2ポインタの終了条件: ptr_a < N かつ ptr_b < M である間ループを回します。どちらか一方の配列を探索し終えた時点で、これ以上共通要素は見つからないため探索を終了して問題ありません。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    M = int(data[1])

    A = [int(x) for x in data[2 : 2 + N]]
    B = [int(x) for x in data[2 + N : 2 + N + M]]

    A.sort()
    B.sort()

    # 第一目標の判定：すべての配達依頼に割り当て可能か
    for i in range(M):
        if A[N - M + i] < B[i]:
            print(-1)
            return

    # 第二目標：ぴったりの最大数（共通要素の数）を尺取り法でカウント
    ans = 0
    ptr_a = 0
    ptr_b = 0
    while ptr_a < N and ptr_b < M:
        if A[ptr_a] == B[ptr_b]:
            ans += 1
            ptr_a += 1
            ptr_b += 1
        elif A[ptr_a] < B[ptr_b]:
            ptr_a += 1
        else:
            ptr_b += 1

    print(ans)


if __name__ == "__main__":
    solve()

---

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