判定問題

まずは「与えられた依頼を全て守ることができるか？」という判定問題を考えます。

これは「タスクを頂点とし、全ての \((j,k)\) について\(P_{j,k}\) から \(P_{j,k+1}\) への有向辺を持つグラフが DAG か（有向サイクルを持たないか）？」と等価です。

グラフの DAG 判定は「『入次数が \(0\) である頂点を削除する』を繰り返すことで全ての頂点を削除できるか？」により行うことができ、次のような実装により \(O(頂点数+辺数)\) で行うことができます。

function is_DAG(G):
  # G: グラフの隣接リスト

  # 入次数を求める
  indegree = [0, 0, ..., 0]
  for v in 1..N:
    for vv in G[v]:
      indegree[vv] += 1

  # 入次数が0の頂点を求める
  Q = Queue
  for v in 1..N:
    if indegree[v] == 0:
      Q.push(v)

  # 入次数0の頂点を削除
  delete_count = 0
  while Q is not empty:
    v = Q.pop()
    delete_count += 1
    for vv in G[v]:
      indegree[vv] -= 1
      if indegree[vv] == 0:
        Q.push(vv)

  return delete_count == N

与えられたグラフがDAGであるとき、依頼を守るタスクの順序はトポロジカルソートにより得ることができます。

フィルタの強さ

続いて、フィルタの強さを考えます。 守るべき依頼の集合が変化するのは、ある依頼がフィルタされるかされないかが変わるとき、すなわちフィルタの強さがいずれかの依頼の優先度と一致したときのみなので、フィルタの強さとして考慮すべき値は高々 \(M\) 種類です。
また、フィルタを強くすればするほど守るべき依頼の個数が減るので、スケジュールが存在するかどうかはフィルタの強さによって単調です。よって二分探索を行うことができ、「DAGか？」の判定問題を \(O(\log M)\) 回解くことで求めることができます。

元の問題

各依頼が届くごとにこの計算を行うことで、計算量は \(O(M\log M(N+\sum_i K_i))\) となります。

以下の実装例では、DAG判定とトポロジカルソートを求めることをまとめて行っています。

実装例 (C++)

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

int main(){
  int n, m;
  cin >> n >> m;

  vector<pair<int,vector<int>>>data;

  auto toposo = [&](int start){
    // data[start:] から作られるグラフのトポロジカルソート順を返す
    // グラフがDAGでないなら途中の(長さN未満の)配列を返す
    vector<vector<int>> G(n);
    for(int i=start; i<data.size(); i++){
      auto&[w, p] = data[i];
      int k = p.size();
      for(int i=0; i<k-1; i++) G[p[i]].push_back(p[i+1]);
    }
    vector<int> indeg(n);
    for(int v=0; v<n; v++){
      for(auto vv: G[v]){
        indeg[vv]++;
      }
    }
    queue<int> q;
    vector<int> ans;
    for(int i=0; i<n; i++)if(indeg[i] == 0) q.push(i);
    while(q.size()){
      int v = q.front(); q.pop();
      ans.push_back(v);
      for(auto vv: G[v]){
        indeg[vv]--;
        if(indeg[vv] == 0) q.push(vv);
      }
    }
    return ans;
  };

  auto solve=[&](){
    // フィルタの強さと、そのときのタスク順序
    int ng = -1, ok = data.size(); // data[i:]でdagか？
    vector<int> toposo_index;
    while(ok-ng > 1){
      int mid = (ok+ng) / 2;
      auto temp = toposo(mid);
      if(temp.size() == n){
        ok = mid;
        toposo_index = temp;
      }else{
        ng = mid;
      }
    }
    return make_pair(ng==-1 ? 0 : data[ng].first, toposo_index);
  };

  for(int i=0; i<m; i++){
    int w, k;
    cin >> w >> k;
    vector<int> p(k);
    for(int j=0; j<k; j++){
      cin >> p[j];
      p[j]--;
    }
    // w でのソート順を保って data に挿入
    auto wp = make_pair(w, p);
    auto it = lower_bound(data.begin(), data.end(), wp);
    data.insert(it, wp);
    auto[x,q] = solve();
    cout << x << " \n"[i==m-1];
    if(i == m-1){
      for(int j=0; j<n; j++){
        cout << q[j]+1 << " \n"[j==n-1];
      }
    }
  }
}

実装例 (Python)

from bisect import insort
N, M = map(int, input().split())
data = []

def toposo(start):
  # data[start:] から作られるグラフのトポロジカルソート順を返す
  # グラフがDAGでないなら途中の(長さN未満の)配列を返す
  G = [[] for _ in range(N)]
  for w, p in data[start:]:
    for i in range(len(p)-1):
      G[p[i]].append(p[i+1])
  
  indeg = [0] * N
  for v in range(N):
    for vv in G[v]:
      indeg[vv] += 1

  ans = []
  for i in range(N):
    if indeg[i] == 0:
      ans.append(i)
  for v in ans:
    for vv in G[v]:
      indeg[vv] -= 1
      if indeg[vv] == 0:
        ans.append(vv)
  return ans

def solve():
  # フィルタの強さと、そのときのタスク順序
  # data[i:]でdagか？
  ng = -1
  ok = len(data)
  toposo_index = []
  while ok-ng > 1:
    mid = (ok+ng) // 2
    temp = toposo(mid)
    if len(temp) == N:
      ok = mid
      toposo_index = temp
    else:
      ng = mid
  return (0 if ng==-1 else data[ng][0], toposo_index)

X = []
Q = []
for _ in range(M):
  W, _, *P = map(int, input().split())
  P = [p-1 for p in P]
  # w でのソート順を保って data に挿入
  insort(data, (W, P))
  x, q = solve()
  X.append(x)
  Q = q

print(*X)
Q = [q+1 for q in Q]
print(*Q)