公式

E - 印刷工場のスケジュール / Print Factory Schedule 解説 by kyopro_friends

この問題は答えを二分探索することで解くことができます。

「 \(D\) 日以内に完了できるか？」という判定問題を考えます。

ポスターの印刷機への割り当てを \(W\) の昇順に「そのポスター を割り当てることが可能な印刷機のうち、 \(R\) が最小のものから貪欲に割り当てる」(★)として決めます。\(D\) 日以内に完了できるなら、この方法により必ず割り当てを求めることができます。

証明 全ての $i$ について、$C_i$ 枚のポスターを全て相異なるものとみなし、$\sum C_i$ 種類のポスターそれぞれについて、印刷機への割り当てを考える。また、$W$ や $R$ などでの比較は適当なタイブレークにより順序が一意に定まるものとする。

ポスターの印刷機への割り当てを任意に1つ取り☆とする。☆と★で印刷機への割り当て方が異なるポスターがあれば、そのうち $W$ が最小のポスターを $i$ であるとする。★でポスター $i$ が割り当てられている印刷機を $j$ とする。このとき、☆に対して適当な操作をすることで、幅が $W$ より小さいポスターの割り当てを変更することなく、ポスター $i$ の割り当てを印刷機 $j$ に変更できることを示す。

①☆で印刷機 $j$ にまだ空きがあれば、ポスター $i$ の割り当てを印刷機 $j$ に変更することができる。

②☆で印刷機 $j$ に空きがないとき、☆でポスター $i$ が割り当てられている印刷機を $j'$ とする。$W$ の最小性の仮定から、印刷機 $j$ に割り当てられているポスター $i'$ であって、$W_i \leq W_{i'}$ であるものが存在する。このとき、★の割り当て方から $R_j \leq R_{j'}$、☆の割り当てから $L_{j'} \leq W_i \leq R_{j'}$ 及び $L_j \leq W_{i'} \leq R_j$ が成り立つので $L_{j'} \leq W_i \leq W_{i'} \leq R_j \leq R_{j'}$ であり、ポスター $i'$ は印刷機 $j'$ に割り当てることができる。よってポスター $i$ とポスタ $i'$ の割り当てを入れ替えることで、ポスター $i$ の割り当てを印刷機 $j$ に変更することができる。

以上の操作を繰り返すことで、☆を★に一致させることができる。

この割り当て方は高速にシミュレーションすることができます。具体的には、印刷機を \(L\) の昇順にソートし、ポスターを \(W\) の昇順に見ながら、各印刷機の残りの容量と「いま見ているポスターを処理することができる印刷機を \(R\) の昇順に取り出せる優先度付きキュー」を更新すればよいです。

以上により、 \(O((N+M)\log M\log \sum C_i+N\log N)\) 時間でこの問題を解くことができます。

実装例 (C++)

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<array<int, 2>> wc(n);
  for(int i=0; i<n; i++) cin >> wc[i][0] >> wc[i][1] >> wc[i][1];
  sort(wc.begin(), wc.end());
  vector<array<int, 2>> lr(m);
  for(int i=0; i<m; i++) cin >> lr[i][0] >> lr[i][1];
  sort(lr.begin(), lr.end());
  
  auto solve=[&](int mid){
    priority_queue<array<int,2>>q;
    int pos=0;
    for(int i=0; i<n; i++){
      auto [w, c] = wc[i];
      while(pos < m && lr[pos][0] <= w){
        q.push({-lr[pos][1], mid});
        pos++;
      }
      while(c){
        if(q.empty()){
          return false;
        }
        auto[r, cnt]=q.top(); q.pop();
        r = -r;
        if(w <= r){
          int x = min(c, cnt);
          c -= x;
          cnt -= x;
          if(cnt > 0){
            q.push({-r, cnt});
          }
        }
      }
    }
    return true;
  };
  
  const int INF = 1e9 + 1;
  int ok = INF, ng = 0;
  while(ok - ng > 1){
    int mid = (ok + ng) / 2;
    if(solve(mid)){
      ok = mid;
    }else{
      ng = mid;
    }
  }

  if(ok == INF){
    cout << -1 << endl;
  }else{
    cout << ok << endl;
  }
}

Python の場合、実装時間制限がきついため、例えば input ではなく stdin.readline を使うなどの工夫が必要であることに注意してください。

実装例 (Python)

import heapq
from sys import stdin
input = stdin.readline

N, M = map(int, input().split())
WC = []
for _ in range(N):
  W, _, C = map(int, input().split())
  WC.append((W, C))
WC.sort()
LR = [tuple(map(int,input().split())) for _ in range(M)]
LR.sort()

def solve(mid):
  q = []
  pos = 0
  for w, c in WC:
    while pos < M and LR[pos][0] <= w:
      heapq.heappush(q, (LR[pos][1], mid))
      pos += 1
    while c:
      if len(q) == 0:
        return False
      R, cnt = heapq.heappop(q)
      if w <= R:
        x = min(c, cnt)
        c -= x
        cnt -= x
        if cnt > 0:
          heapq.heappush(q, (R, cnt))
  return True

INF = 10**9 + 1
ok = INF
ng = 0
while ok - ng > 1:
  mid = (ok + ng) // 2
  if solve(mid):
    ok = mid
  else:
    ng = mid

if ok == INF:
  print(-1)
else:
  print(ok)

投稿日時:
最終更新: