概要

この問題は、\(M\) 人のアルバイトを \(N\) 日間のシフトに割り当て、全員が自身のスキルレベル以下の要求を持つ日に働くという条件のもとで、得られる利益を最大化する問題です。

これは「二部グラフの最大重みマッチング」の問題として捉えることができますが、制約が \(N, M \leq 2 \times 10^5\) と大きいため、一般的な最大流アルゴリズムでは間に合いません。スキルの条件が直線的（スキルが高い人は低い要求の仕事を兼ねられる）であることを利用し、貪欲法とデータ構造（遅延評価セグメント木）を組み合わせて効率的に解きます。

考察

1. 貪欲法の適用

この問題は「独立システム」の一種であるマトロイド（横断マトロイド）の構造を持っています。マトロイド上の最大重み独立集合を求める問題は、重みが大きい要素から順に、独立性を保てるなら追加するという貪欲法で最適解が得られることが知られています。

したがって、以下の手順で考えます。 1. 営業日を売上 \(S_i\) の降順にソートする。 2. 売上が高い日を順に見ていき、「その日をこれまでに選んだ日の集合に加えても、全員を割り当てることが可能か」を判定する。 3. 可能であればその日を追加し、最終的に \(M\) 日選べればその合計利益を出力、選べなければ -1 を出力する。

2. 割り当て可能かどうかの判定条件（ホールの結婚定理の応用）

「選んだ日の集合 \(D\) に対して、全員を割り当て可能か」という条件を効率的に判定する必要があります。 スキルの要求レベル \(H_i\) とアルバイトのスキル \(P_j\) をソートして考えると、以下の条件が導かれます。

あるスキルレベル \(x\) 以上の要求を持つ日の数を \(countD(x)\)、スキルレベル \(x\) 以上のアルバイトの人数を \(countP(x)\) とすると、すべての \(x\) について以下の不等式が成り立つ必要があります。 $\(countD(x) \leq countP(x)\)$

もしある \(x\) で \(countD(x) > countP(x)\) となると、その \(x\) 以上の要求を満たせるアルバイトが不足していることを意味するため、割り当ては不可能です。

3. データ構造による高速化

選ぶ日を増やすたびにすべての \(x\) についてチェックすると時間がかかりすぎます。そこで、遅延評価セグメント木を利用します。

• ユニークな \(H_i\) の値を座標圧縮して管理します。
• セグメント木の各ノードには \(f(x) = countP(x) - countD(x)\) の値を保持させます。
• 初期状態では \(countD(x) = 0\) なので、セグメント木には \(countP(x)\) をセットしておきます。
• ある要求レベル \(H_i\) の日を追加するとき、そのレベル以下のすべての \(x\) に対して \(countD(x)\) が \(1\) 増えるため、\(f(x)\) は \(1\) 減少します。
• つまり、範囲 \([0, \text{rank}(H_i)]\) に対して \(-1\) の区間更新を行い、その範囲の最小値が \(0\) 未満にならないかを確認すればよいことになります。

アルゴリズム

1. 準備:
   • アルバイトのスキル \(P_j\) をソートします。
   • 営業日の要求スキル \(H_i\) のユニークな値を取り出し、ソートして座標圧縮用の辞書を作ります。
   • 各 \(H_i\) について、それを満たせるアルバイト数 \(C_k = |\{j \mid P_j \geq H_i\}|\) を計算します。
2. セグメント木の初期化:
   • \(C_k\) を初期値とする遅延評価セグメント木を作成します。この木は「区間加算」と「区間最小値取得」をサポートします。
3. 貪欲な選択:
   • 営業日を売上 \(S_i\) の降順にソートします。
   • 各営業日 \((H_i, S_i)\) について：
     • セグメント木の範囲 \([0, \text{rank}(H_i)]\) の最小値が \(0\) より大きいか確認します。
     • \(0\) より大きければ、その範囲に \(-1\) を加算（更新）し、利益に \(S_i\) を加え、選択した日数をカウントします。
     • 選択した日数が \(M\) に達したら終了します。
4. 出力:
   • 最終的に \(M\) 日選べていれば合計利益を、そうでなければ -1 を出力します。

計算量

• 営業日とアルバイトのソート: \(O(N \log N + M \log M)\)
• 座標圧縮と初期値計算: \(O(N \log M)\) （二分探索を利用）
• セグメント木の操作（\(N\) 回の更新とクエリ）: \(O(N \log N)\)
• 合計時間計算量: \(O(N \log N + M \log M)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• Python 3 で実行する場合、再帰的なセグメント木は遅いため、非再帰（ループ）形式のセグメント木を使用すると高速です。

• \(countP(x)\) の計算には bisect_left を用いることで、各スキルレベル以上の人数を高速に求められます。

• 売上の高い順に \(M\) 個選ぶ際、条件を満たさない日はスキップし、最終的に \(M\) 個に満たない場合は割り当て不可と判断します。

  ソースコード

import sys
import bisect

# We use an iterative segment tree to ensure it's fast enough for Python 3.
# The problem can be modeled as finding the maximum weight independent set of size M
# in a transversal matroid where days are matchable to workers.

def solve():
    # Read all input data at once for speed
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    days = []
    ptr = 2
    for i in range(N):
        h = int(input_data[ptr])
        s = int(input_data[ptr+1])
        days.append((h, s))
        ptr += 2
    
    P = []
    for i in range(M):
        P.append(int(input_data[ptr]))
        ptr += 1
    
    # Sorting workers by skill level to facilitate counting
    P.sort()
    
    # Unique H values for the segment tree indexing
    H_vals = sorted(list(set(d[0] for d in days)))
    rank = {h: i for i, h in enumerate(H_vals)}
    L = len(H_vals)
    
    # Precalculate C_k = number of workers who can handle a day with skill level H_vals[k]
    # This is equivalent to |{P_j : P_j >= H_vals[k]}|
    C = [M - bisect.bisect_left(P, h) for h in H_vals]
    
    # Iterative Lazy Segment Tree for range addition and range minimum.
    # We maintain the condition: countD(x) <= countP(x) for all x.
    # This is equivalent to C_k - countD(H_vals[k]) >= 0.
    class LazySegmentTree:
        def __init__(self, data):
            self.n_orig = len(data)
            self.n = 1 << (self.n_orig - 1).bit_length() if self.n_orig > 1 else 1
            self.h = self.n.bit_length() - 1
            self.tree = [0] * (2 * self.n)
            self.lazy = [0] * self.n
            for i in range(self.n_orig):
                self.tree[self.n + i] = data[i]
            # Fill padding elements with infinity to avoid affecting range minimums
            for i in range(self.n_orig, self.n):
                self.tree[self.n + i] = 10**18
            for i in range(self.n - 1, 0, -1):
                self.tree[i] = min(self.tree[2 * i], self.tree[2 * i + 1])

        def _apply(self, p, v):
            self.tree[p] += v
            if p < self.n:
                self.lazy[p] += v

        def _build(self, p):
            while p > 1:
                p >>= 1
                self.tree[p] = min(self.tree[2 * p], self.tree[2 * p + 1]) + self.lazy[p]

        def _push(self, p):
            for s in range(self.h, 0, -1):
                i = p >> s
                if self.lazy[i] != 0:
                    self._apply(2 * i, self.lazy[i])
                    self._apply(2 * i + 1, self.lazy[i])
                    self.lazy[i] = 0

        def update(self, l, r, v):
            if v == 0: return
            l += self.n
            r += self.n
            l0, r0 = l, r
            while l < r:
                if l & 1:
                    self._apply(l, v)
                    l += 1
                if r & 1:
                    r -= 1
                    self._apply(r, v)
                l >>= 1
                r >>= 1
            self._build(l0)
            self._build(r0 - 1)

        def query(self, l, r):
            l += self.n
            r += self.n
            self._push(l)
            self._push(r - 1)
            res = 10**18
            while l < r:
                if l & 1:
                    res = min(res, self.tree[l])
                    l += 1
                if r & 1:
                    r -= 1
                    res = min(res, self.tree[r])
                l >>= 1
                r >>= 1
            return res

    st = LazySegmentTree(C)
    
    # Sort days by profit in descending order to apply the matroid greedy algorithm
    days.sort(key=lambda x: x[1], reverse=True)
    
    total_profit = 0
    count = 0
    for h, s in days:
        r = rank[h]
        # Check if adding this day maintains the matching condition for all workers
        # The condition is that for all k <= r, C_k - countD(H_vals[k]) must be > 0.
        if st.query(0, r + 1) > 0:
            st.update(0, r + 1, -1)
            total_profit += s
            count += 1
            # Once we've assigned all M workers, we stop.
            if count == M:
                break
    
    # If we managed to assign all M workers, output the maximum profit.
    if count == M:
        print(total_profit)
    else:
        print("-1")

if __name__ == '__main__':
    solve()

---

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