概要

\(N\) 人の配達員を \(M\) 件の配達依頼に割り当てる問題で、まず全件割り当て可能か判定し、可能なら「ぴったり（\(A_i = B_j\)）」の割り当て数を最大化します。

考察

重要な気づき 1: 実行可能性の判定

全件割り当て可能かどうかは、貪欲法で判定できます。\(A\) と \(B\) をソートし、大きい方から順にマッチングを試みます。\(B\) の大きい値から順に、それを満たせる最小の \(A\) を割り当てるのが最適です。

具体的には、\(A\) と \(B\) を降順に見て、\(A[i] \geq B[j]\) なら割り当て成功として両方進め、そうでなければ \(A\) だけ進めます。最終的に全ての \(B\) が割り当てられれば実行可能です。

重要な気づき 2: ぴったりの最大数

各値 \(v\) について、\(A\) に \(v\) が \(c_A(v)\) 個、\(B\) に \(v\) が \(c_B(v)\) 個あるとき、値 \(v\) でのぴったりマッチ数は最大 \(\min(c_A(v), c_B(v))\) です。

核心的な洞察: 全ての値について可能な限りぴったりマッチを使っても、残りの割り当ての実行可能性は保たれます。

なぜ実行可能性が保たれるか（直感的説明）

ぴったりマッチ（\(A_i = B_j = v\)）を取り除くことは、\(A\) と \(B\) から同じ値の要素を同数だけ除去することに相当します。例えば：

• \(A = [1, 2, 3, 3, 5]\), \(B = [2, 3, 4]\) の場合
• ぴったりマッチ: 値2で1組、値3で1組（合計2組）
• 残り: \(A = [1, 3, 5]\), \(B = [4]\) → \(5 \geq 4\) で割り当て可能

同じ値を両方から除去しても、「\(B[j]\) 以上の \(A\) の個数」と「\(B[j]\) 以上の \(B\) の個数」の差は変わらない（または改善する）ため、実行可能性が維持されます。

アルゴリズム

1. \(A\) と \(B\) をソートする
2. 貪欲法で実行可能性を判定（不可能なら -1 を出力）
3. \(A\) と \(B\) の各値の出現回数をカウント
4. 各値 \(v\) について \(\min(c_A(v), c_B(v))\) を合計し、それが答え

答え = Σ min(count_A[v], count_B[v])  (v は B に出現する全ての値)

計算量

• 時間計算量: \(O(N \log N + M \log M)\)（ソートが支配的）
• 空間計算量: \(O(N + M)\)（カウンター用）

実装のポイント

• 実行可能性の判定: 配列末尾（大きい値）から走査する貪欲法を使います。2つのポインタ \(i\), \(j\) を末尾から動かし、\(A[i] \geq B[j]\) なら両方進め、そうでなければ \(i\) のみ進めます。

• Counter の活用: Python の collections.Counter を使うと、各値の出現回数を簡潔に求められます。

• 入力の高速化: sys.stdin.buffer.read() を用いてまとめて読み込み、大量データでもTLEを回避しています。

  ソースコード

from collections import Counter

def solve():
    import sys
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(M)]; idx += M
    
    A.sort()
    B.sort()
    
    # First check if assignment is possible at all using greedy matching
    # Match largest B with smallest sufficient A (greedy from right)
    # Standard check: sort both, try to match B[j] with A[i] where A[i] >= B[j]
    # Greedy: iterate from the end
    
    # Check feasibility: for each j from M-1 to 0, we need A[i] >= B[j]
    # Greedy feasibility check: match B sorted desc with A sorted desc
    j = M - 1
    i = N - 1
    while j >= 0 and i >= 0:
        if A[i] >= B[j]:
            j -= 1
            i -= 1
        else:
            i -= 1
    
    if j >= 0:
        print(-1)
        return
    
    # Now maximize the number of exact matches (A[i] == B[j])
    # Count exact matches available
    count_a = Counter(A)
    count_b = Counter(B)
    
    # Maximum possible exact matches
    max_exact = sum(min(count_a[v], count_b[v]) for v in count_b)
    
    # But we need to check if we can achieve max_exact exact matches while still
    # being able to assign the remaining B's to remaining A's.
    
    # Binary search on the number of exact matches: can we achieve at least k exact matches?
    # Actually, let's think differently. We want to maximize exact matches.
    # 
    # Key insight: We can binary search on the answer k.
    # For a given k exact matches, we need to verify feasibility.
    # 
    # Better approach: try to use as many exact matches as possible.
    # We can binary search: is it possible to have at least k exact matches?
    #
    # For checking: we decide to make k exact matches. We want to maximize exact,
    # so we try k = max_exact and decrease if not feasible.
    #
    # Actually, let's think about it greedily.
    # Sort A and B. For each value v, we can use min(count_a[v], count_b[v]) exact matches.
    # After removing exact-matched pairs, we need to match remaining B's with remaining A's
    # such that A[i] >= B[j]. This is always possible if the original full matching is possible
    # and we only removed equal pairs.
    #
    # Proof: If we remove k pairs where A[i]=B[j], the remaining A's and B's still satisfy
    # the feasibility condition. Because for the remaining sorted arrays, removing equal
    # elements from both sides preserves the greedy matching property.
    
    # Let me verify: after removing all possible exact matches, check if remaining can be matched.
    # Build remaining A and B after removing exact matches.
    
    remaining_a = []
    remaining_b = []
    
    used_a = Counter()
    for v in count_b:
        exact = min(count_a[v], count_b[v])
        used_a[v] = exact  # exact matches used from A for value v
    
    # Remaining A: for each value, count_a[v] - used_a[v]
    # Remaining B: for each value v, count_b[v] - min(count_a[v], count_b[v])
    
    for v in sorted(count_a):
        rem = count_a[v] - used_a.get(v, 0)
        remaining_a.extend([v] * rem)
    
    for v in sorted(count_b):
        exact = min(count_a[v], count_b[v])
        rem = count_b[v] - exact
        remaining_b.extend([v] * rem)
    
    # Check if remaining can be matched
    j2 = len(remaining_b) - 1
    i2 = len(remaining_a) - 1
    while j2 >= 0 and i2 >= 0:
        if remaining_a[i2] >= remaining_b[j2]:
            j2 -= 1
            i2 -= 1
        else:
            i2 -= 1
    
    if j2 >= 0:
        # This shouldn't happen if the overall matching is feasible and we only removed equal pairs
        # But just in case, we could reduce exact matches. For safety:
        # Actually this can't happen. Removing equal pairs preserves feasibility.
        # But let me handle it anyway - shouldn't reach here.
        print(-1)
        return
    
    print(max_exact)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。