概要

\(N\) 個のタスクの順列（スケジュール）を作る際に、優先度付きの順序制約を無視できるフィルタの強さ \(X\) の最小値を、依頼が1件ずつ届くたびに求める問題です。核心は「選んだ \(X\) で残る制約がDAG（有向非巡回グラフ）を成すか」の判定にあります。

考察

守るべき制約とDAG

依頼 \(j\) の順序制約「\(P_{j,1} \to P_{j,2} \to \cdots \to P_{j,K_j}\)」は、連続する2タスク間の有向辺 \(P_{j,i} \to P_{j,i+1}\) の集まりとみなせます。

すべての有効な制約（\(W_j > X\) のもの）から辺を集めてグラフを作ったとき、有効なスケジュールが存在する ⟺ そのグラフがDAGである（トポロジカル順序が存在する）ことがわかります。グラフに閉路があると、どう並べても矛盾するからです。

\(X\) の候補値

\(X\) を大きくするほど無視する依頼が増え、辺が減ります。制約の集合が変化するのは \(X\) が何らかの \(W_j\) をまたいだときだけなので、\(X\) の候補は \(\{0, W_1, W_2, \ldots, W_t\}\) の高々 \(t+1\) 個に限られます。

二分探索

候補値をソートすると、\(X\) が大きいほど制約が緩くなるため、DAG判定の結果は単調（ある閾値以上で常に成功）です。よって二分探索で最小の \(X\) を効率的に求められます。

アルゴリズム

各 \(t = 1, 2, \ldots, M\) について：

1. 依頼 \(1, \ldots, t\) の優先度 \(W_1, \ldots, W_t\) を集め、重複を除いてソートする。
2. まず \(X = 0\) で全制約がDAGか判定。DAGなら \(X_t = 0\)。
3. そうでなければ、候補値の列に対して二分探索を行う。各候補 \(X\) に対し：
   • \(W_j > X\) である依頼 \(j\) から辺を集めてグラフを構築
   • Kahnのアルゴリズム（BFSベースのトポロジカルソート）でDAG判定
   • 処理できたノード数が \(N\) なら DAG（成功）
4. 二分探索で最小の成功する \(X\) を求める。

最後に、\(X_M\) でフィルタした制約に対するトポロジカル順序を出力する（制約に関係しないタスクも順序に含めることで \(N\) 個の順列を得る）。

DAG判定の具体例（\(N=3\), 制約: \(1 \to 2\), \(2 \to 1\)）：

• 辺 \(1 \to 2\) と \(2 \to 1\) で閉路が存在 → DAGでない → この \(X\) では不可

計算量

• 各時点 \(t\) で二分探索は \(O(\log M)\) 回
• 各判定でグラフ構築＋トポロジカルソートに \(O(N + \sum K_j)\)
• 全体で \(M\) 時点を処理

\[\text{時間計算量: } O\!\left(M \cdot \log M \cdot \left(N + \sum_{j=1}^{M} K_j\right)\right)\]

制約上限を代入すると \(O(1000 \times 10 \times 5000) = O(5 \times 10^7)\) 程度。

• 空間計算量: \(O\!\left(N + \sum K_j\right)\)（グラフ格納用）

実装のポイント

• 多重辺への対応: 異なる依頼が同じ辺 \(u \to v\) を生む可能性がありますが、Kahnのアルゴリズムは入次数の増減で管理するため、多重辺があっても正しく動作します。

• トポロジカル順序の出力: getOrder 関数はBFSでトポロジカル順序を求めます。入次数 \(0\) のノードから順にキューに入れるため、制約に現れないタスクも自然に順列に含まれます。

• \(X = 0\) の特別処理: 二分探索の前に \(X = 0\) を先に判定し、全制約を守れる場合を正しく扱っています。

  ソースコード

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

int main(){
    int N, M;
    scanf("%d%d", &N, &M);
    
    vector<int> W(M);
    vector<vector<int>> P(M);
    
    for(int j = 0; j < M; j++){
        int K;
        scanf("%d%d", &W[j], &K);
        P[j].resize(K);
        for(int i = 0; i < K; i++){
            scanf("%d", &P[j][i]);
            P[j][i]--;
        }
    }
    
    auto check = [&](int t, int X) -> bool {
        vector<vector<int>> adj(N);
        vector<int> indeg(N, 0);
        for(int j = 0; j < t; j++){
            if(W[j] > X){
                for(int i = 0; i+1 < (int)P[j].size(); i++){
                    adj[P[j][i]].push_back(P[j][i+1]);
                    indeg[P[j][i+1]]++;
                }
            }
        }
        queue<int> q;
        for(int i = 0; i < N; i++) if(indeg[i] == 0) q.push(i);
        int cnt = 0;
        while(!q.empty()){
            int u = q.front(); q.pop();
            cnt++;
            for(int v : adj[u]){
                if(--indeg[v] == 0) q.push(v);
            }
        }
        return cnt == N;
    };
    
    auto getOrder = [&](int t, int X) -> vector<int> {
        vector<vector<int>> adj(N);
        vector<int> indeg(N, 0);
        for(int j = 0; j < t; j++){
            if(W[j] > X){
                for(int i = 0; i+1 < (int)P[j].size(); i++){
                    adj[P[j][i]].push_back(P[j][i+1]);
                    indeg[P[j][i+1]]++;
                }
            }
        }
        queue<int> q;
        for(int i = 0; i < N; i++) if(indeg[i] == 0) q.push(i);
        vector<int> order;
        while(!q.empty()){
            int u = q.front(); q.pop();
            order.push_back(u);
            for(int v : adj[u]){
                if(--indeg[v] == 0) q.push(v);
            }
        }
        return order;
    };
    
    vector<int> answers(M);
    
    for(int t = 1; t <= M; t++){
        vector<int> ws;
        for(int j = 0; j < t; j++) ws.push_back(W[j]);
        sort(ws.begin(), ws.end());
        ws.erase(unique(ws.begin(), ws.end()), ws.end());
        
        if(check(t, 0)){
            answers[t-1] = 0;
        } else {
            int lo = 0, hi = (int)ws.size() - 1;
            while(lo < hi){
                int mid = (lo + hi) / 2;
                if(check(t, ws[mid])) hi = mid;
                else lo = mid + 1;
            }
            answers[t-1] = ws[lo];
        }
    }
    
    for(int t = 0; t < M; t++){
        printf("%d%c", answers[t], t+1<M?' ':'\n');
    }
    
    vector<int> order = getOrder(M, answers[M-1]);
    for(int i = 0; i < N; i++){
        printf("%d%c", order[i]+1, i+1<N?' ':'\n');
    }
    
    return 0;
}

---

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