概要

この問題は、各発表者の開始時刻を 2 つの候補から選ぶことで、指定された \(M\) 組の発表者間の開始時刻の差の最小値（\(f(S)\)）を最大化し、その最大値 \(K\) を達成する辞書順最小の選択パターン \(S\) を求める問題です。

「最小値の最大化」という構造から二分探索が、また「2つの選択肢から1つを選ぶ」という制約から 2-SAT が有効な手法となります。

考察

1. \(f(S)\) の最大化（二分探索）

「\(f(S)\) を \(X\) 以上にできるか？」という判定問題を考えます。 \(f(S) \geq X\) であるためには、与えられた \(M\) 組のすべての対 \((U_j, V_j)\) について、その開始時刻の差の絶対値が \(X\) 以上である必要があります。

各発表者 \(i\) は「時刻 \(A_i\)（選択 0）」または「時刻 \(A_i + D_i\)（選択 1）」のどちらか一方を選びます。これは、発表者 \(i\) に対応する論理変数 \(x_i\) を用意し、真偽値で選択を表す 2-SAT (2-Satisfiability) の問題としてモデル化できます。

具体的には、ある対 \((U_j, V_j)\) について、以下の 4 通りの組み合わせのうち、時刻差が \(X\) 未満になるものを「禁止」します。 - \(U_j\) が \(S_{U_j}\)、\(V_j\) が \(S_{V_j}\) を選んだ時の差が \(X\) 未満なら、\((S_{U_j} \text{ かつ } S_{V_j})\) という状態は許されません。 - これは論理式で \(\neg (S_{U_j} \land S_{V_j})\) となり、\((\neg S_{U_j} \lor \neg S_{V_j})\) という 2-SAT の節（clause）に変換できます。

この判定問題を二分探索で解くことで、最大値 \(K\) を求めることができます。

2. 辞書順最小の \(S\) の構成（貪欲法）

最大値 \(K\) が求まったら、次は \(f(S) \geq K\) を満たしつつ、文字列 \(S\) を辞書順最小にします。辞書順最小を求める定石は、「前の文字から順に、可能な限り小さい値（’0’）を割り当てていく」 という貪欲な手法です。

1. \(i = 1\) から \(N\) まで順に、発表者 \(i\) の選択を決定する。
2. まず \(S_i = 0\) と仮定し、以下の条件を満たす \(S_{i+1}, \dots, S_N\) の割り当てが存在するかを判定する。
   • すでに決定した \(S_1, \dots, S_i\) の値と矛盾しない。
   • すべての対の時刻差が \(K\) 以上である。
3. 判定には再び 2-SAT を使います。\(S_i = 0\) を固定するには、2-SAT の節として \((S_i=0 \lor S_i=0)\) を追加すればよいです。
4. \(S_i = 0\) で可能なら確定させ、不可能なら \(S_i = 1\) と確定させます。

アルゴリズム

1. 二分探索:
   • 範囲 \([0, 2 \times 10^9]\) で \(X\) を二分探索する。
   • check(X) 内で、各対 \((U_j, V_j)\) の 4 パターンの時刻差を確認し、差が \(X\) 未満の組み合わせを 2-SAT の制約として追加する。
   • 強連結成分分解 (SCC) を用いて 2-SAT が充足可能か判定する。
2. 辞書順最小の決定:
   • 求めた最大値 \(K\) を固定する。
   • \(i=1 \dots N\) について、「\(S_i=0\) を固定しても 2-SAT が充足可能か」を順に判定し、文字列 \(S\) を構築する。

計算量

• 二分探索部分: \(O(\log(\max A_i) \cdot (N + M))\)
• 辞書順最小部分: \(O(N \cdot (N + M))\)
• 全体: \(O((\log(\max A_i) + N) \cdot (N + M))\)

制約 \(N \leq 2000, M \leq 5000\)、および \(N \times M \leq 10^6\) より、全体で数百万回程度の操作となり、実行時間制限内に十分収まります。

実装のポイント

• 2-SAT の構築: 変数 \(i\) に対して、ノード \(2i\) を「選択 1 (True)」、ノード \(2i+1\) を「選択 0 (False)」のように割り当てます。

• 制約の追加: 「\(x\) と \(y\) の同時成立を禁止する」という制約は、\(\neg (x \land y) \equiv (\neg x \lor \neg y)\) となり、これは含意関係 \((\text{if } x \text{ then } \neg y)\) および \((\text{if } y \text{ then } \neg x)\) としてグラフに辺を張ります。

• SCC: 2-SAT の充足可能性判定には、KosarajuのアルゴリズムやTarjanのアルゴリズムを用いた強連結成分分解が必要です。同じ変数の True ノードと False ノードが同じ強連結成分に含まれていなければ充足可能です。

• \(M=0\) のケース: 問題文の定義に従い、\(M=0\) のときは \(K=0\) とし、辞書順最小として 00...0 を出力するように注意します。

  ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// The maximum number of nodes in the implication graph is 2 * N, where N <= 2000.
const int MAXNV = 4005;

// Global adjacency and reverse adjacency lists for Kosaraju's algorithm.
vector<int> adj[MAXNV];
vector<int> rev_adj[MAXNV];
int component[MAXNV];
bool visited[MAXNV];
int order[MAXNV];
int order_ptr;

// First DFS pass of Kosaraju's algorithm to determine the finishing order.
void dfs1(int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs1(v);
    }
    order[order_ptr++] = u;
}

// Second DFS pass of Kosaraju's algorithm on the reverse graph to find SCCs.
void dfs2(int u, int c) {
    component[u] = c;
    for (int v : rev_adj[u]) {
        if (component[v] == -1) dfs2(v, c);
    }
}

// Solves the 2-SAT problem using Kosaraju's algorithm for SCC.
// nv is the total number of nodes (2 * N), and n is the number of variables (N).
bool is_satisfiable(int nv, int n) {
    for (int i = 0; i < nv; ++i) {
        visited[i] = false;
        component[i] = -1;
    }
    order_ptr = 0;
    for (int i = 0; i < nv; ++i) {
        if (!visited[i]) dfs1(i);
    }
    int c = 0;
    for (int i = nv - 1; i >= 0; --i) {
        if (component[order[i]] == -1) dfs2(order[i], c++);
    }
    for (int i = 0; i < n; ++i) {
        // A 2-SAT instance is satisfiable if no variable x_i and its negation !x_i are in the same SCC.
        if (component[2 * i] == component[2 * i + 1]) return false;
    }
    return true;
}

// Adds a clause (x_i == f OR x_j == g) to the 2-SAT instance.
// f and g are boolean values representing the required state of x_i and x_j.
void add_clause(int i, bool f, int j, bool g) {
    // x_i is represented by node 2*i (true) and 2*i + 1 (false).
    int node_i_true = 2 * i;
    int node_i_false = 2 * i + 1;
    int node_j_true = 2 * j;
    int node_j_false = 2 * j + 1;

    int u = f ? node_i_true : node_i_false;
    int not_u = f ? node_i_false : node_i_true;
    int v = g ? node_j_true : node_j_false;
    int not_v = g ? node_j_false : node_j_true;

    // The clause (u OR v) is equivalent to (NOT u -> v) and (NOT v -> u).
    adj[not_u].push_back(v);
    adj[not_v].push_back(u);
    rev_adj[v].push_back(not_u);
    rev_adj[u].push_back(not_v);
}

// Builds the 2-SAT graph for a specific threshold X and checks if it's satisfiable.
bool check(long long X, int N, int M, const vector<long long>& A, const vector<long long>& D, 
           const vector<pair<int, int>>& pairs, const vector<pair<int, bool>>& extra_clauses) {
    int nv = 2 * N;
    for (int i = 0; i < nv; ++i) {
        adj[i].clear();
        rev_adj[i].clear();
    }
    // For each given pair of presenters, forbid start time combinations that result in a difference < X.
    for (auto& p : pairs) {
        int u = p.first, v = p.second;
        long long tU0 = A[u], tU1 = A[u] + D[u];
        long long tV0 = A[v], tV1 = A[v] + D[v];
        
        // If |tU - tV| < X, then the combination (S_u, S_v) is forbidden.
        // This is added as a 2-SAT clause: (NOT S_u OR NOT S_v).
        if ((tU0 > tV0 ? tU0 - tV0 : tV0 - tU0) < X) add_clause(u, true, v, true);
        if ((tU0 > tV1 ? tU0 - tV1 : tV1 - tU0) < X) add_clause(u, true, v, false);
        if ((tU1 > tV0 ? tU1 - tV0 : tV0 - tU1) < X) add_clause(u, false, v, true);
        if ((tU1 > tV1 ? tU1 - tV1 : tV1 - tU1) < X) add_clause(u, false, v, false);
    }
    // Add constraints for already fixed presenter choices in the lexicographical search.
    for (auto& ec : extra_clauses) {
        add_clause(ec.first, ec.second, ec.first, ec.second);
    }
    return is_satisfiable(nv, N);
}

int main() {
    // Faster I/O for competitive programming.
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> A(N), D(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> D[i];

    vector<pair<int, int>> pairs(M);
    for (int i = 0; i < M; ++i) {
        cin >> pairs[i].first >> pairs[i].second;
        pairs[i].first--; // Convert to 0-indexed.
        pairs[i].second--;
    }

    // Binary search for the maximum possible minimum difference K.
    long long K = 0;
    if (M > 0) {
        long long low = 0, high = 2000000000LL;
        while (low <= high) {
            long long mid = low + (high - low) / 2;
            if (check(mid, N, M, A, D, pairs, {})) {
                K = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }

    // Output the maximum K.
    cout << K << "\n";

    // Greedy search to find the lexicographically smallest string S that achieves K.
    string S = "";
    vector<pair<int, bool>> extra_clauses;
    for (int i = 0; i < N; ++i) {
        // Try setting S[i] = '0' (choice A_i).
        extra_clauses.push_back({i, false});
        if (check(K, N, M, A, D, pairs, extra_clauses)) {
            S += '0';
        } else {
            // If '0' is not possible, set S[i] = '1' (choice A_i + D_i).
            extra_clauses.pop_back();
            extra_clauses.push_back({i, true});
            S += '1';
        }
    }
    cout << S << "\n";

    return 0;
}

---

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