概要

各発表者は開始時刻を 2 通りから選ぶので、全体は「二値選択」の問題です。
「どのペアでも開始時刻差を少なくとも \(K\) にできるか」を判定問題に落とし、2-SAT + 二分探索で最大値 \(K\) を求め、さらにその \(K\) を満たす中で辞書順最小の文字列を構成します。

考察

この問題で最大化したいのは - 各指定ペア \((U_j, V_j)\) の開始時刻差の絶対値 - その最小値 \(f(S)\)

です。
つまり「最小の差」をできるだけ大きくしたいので、典型的に

• 「\(f(S) \ge K\) を満たす \(S\) が存在するか？」を判定
• 判定可能なら \(K\) を上げる、不能なら下げる

という形が使えます（単調性があるため二分探索可能）。

---

1. 判定問題への変形

発表者 \(i\) の選択を変数 \(x_i \in \{0,1\}\) とします。

• \(x_i=0\) : 時刻 \(A_i\)
• \(x_i=1\) : 時刻 \(A_i + D_i\)

固定した \(K\) に対し、各ペア \((u,v)\) について 4 通りの組合せ \((x_u, x_v)\) を調べます。
もしある組合せで [ |t_u - t_v| < K ] なら、その組合せは「禁止」です。

「\((x_u=su)\) かつ \((x_v=sv)\) を禁止」は論理式で [ \neg(x_u=su \land x_v=sv) \equiv (x_u\ne su)\ \lor\ (x_v\ne sv) ] となり、これは 2-CNF の1節です。
全禁止条件を集めると 2-SAT になるため、充足可能性を線形時間で判定できます。

---

2. 素朴解法が厳しい理由

全探索は \(2^N\) 通りで、\(N \le 2000\) では不可能です。
また \(K\) を 0 から順に試すのも範囲が最大 \(10^9\) オーダーで現実的ではありません。

そこで

• 判定：2-SAT（多項式時間）
• 最適化：二分探索（\(\log\) 回）

を組み合わせて高速化します。

---

3. 辞書順最小の \(S\) の作り方

最大 \(K\) が求まった後、左から順に文字を決めます。

• まず \(S_i=0\) を仮置きして「この接頭辞固定で可解か？」を再度 2-SAT 判定
• 可解なら 0 確定（辞書順を小さくしたい）
• 不可なら 1 にする

これを \(i=1..N\) で繰り返せば、\(f(S)=K\) を満たす中で辞書順最小が得られます。
（0 を置けるときは必ず置く貪欲が正しい）

アルゴリズム

1. 入力を読む。
   
2. \(M=0\) なら制約がないので \(K=0\), \(S=00\cdots0\) を出力。
   
3. feasible(K, prefix) を定義：
   • 2-SAT インスタンスを作る。
   • prefix（先頭何文字かの固定）があれば単位節で追加。
   • 各辺 \((u,v)\)、各 \((su,sv)\in\{0,1\}^2\) について
     \(|t_u(su)-t_v(sv)|<K\) なら禁止節を追加。
   • 2-SAT が satisfiable なら true。
4. \(K\) を二分探索で最大化。
   
5. 得られた \(K\) に対して、各桁を 0 優先の可否判定で決めて辞書順最小文字列を構築。
   
6. \(K\) と \(S\) を出力。

計算量

• 1回の feasible で
  
  • 変数数 \(N\)、節数は各辺あたり最大4個なので \(O(M)\)
    
  • 2-SAT 判定は \(O(N+M)\)
• 二分探索は約 \(\log_2(2\times10^9)\approx 31\) 回
• 辞書順構築でさらに \(N\) 回判定

よって全体は
- 時間計算量: \(O((\log V + N)\,(N+M))\)（\(V\approx 2\times10^9\)）
実質 \(O(N(N+M))\) 寄り（\(N\) 回の判定が支配的） - 空間計算量: \(O(N+M)\)（2-SAT グラフ）

実装のポイント

• 「禁止組合せ」を節に直すときは
  [ (x_u\ne su)\lor(x_v\ne sv) ] を正確に張る（コードでは add_or(u, su^1, v, sv^1)）。

• 絶対値比較は long long で扱う（時刻が最大 \(2\times10^9\) 程度）。

• 辞書順最小化は「各位置で 0 を試して可なら採用」の順序が重要。

• M=0 は特別処理すると不要な判定を省けて安全。

  ソースコード

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

struct TwoSAT {
    int n;
    vector<vector<int>> g, rg;
    vector<int> comp, order, used, assignment;

    TwoSAT(int n = 0) { init(n); }

    void init(int n_) {
        n = n_;
        g.assign(2 * n, {});
        rg.assign(2 * n, {});
    }

    // var i, value v (false=0, true=1) -> node id
    int id(int i, bool v) const { return 2 * i + (v ? 1 : 0); }

    void add_imp(int a, int b) {
        g[a].push_back(b);
        rg[b].push_back(a);
    }

    void add_or(int i, bool vi, int j, bool vj) {
        // (x_i==vi) OR (x_j==vj)
        int a = id(i, vi), na = id(i, !vi);
        int b = id(j, vj), nb = id(j, !vj);
        add_imp(na, b);
        add_imp(nb, a);
    }

    void add_unit(int i, bool vi) {
        // (x_i == vi)
        add_imp(id(i, !vi), id(i, vi));
    }

    bool satisfiable() {
        int V = 2 * n;
        used.assign(V, 0);
        order.clear();
        order.reserve(V);

        for (int s = 0; s < V; s++) if (!used[s]) {
            // iterative DFS for postorder
            vector<pair<int,int>> st;
            st.push_back({s, 0});
            used[s] = 1;
            while (!st.empty()) {
                int v = st.back().first;
                int &it = st.back().second;
                if (it < (int)g[v].size()) {
                    int to = g[v][it++];
                    if (!used[to]) {
                        used[to] = 1;
                        st.push_back({to, 0});
                    }
                } else {
                    order.push_back(v);
                    st.pop_back();
                }
            }
        }

        comp.assign(V, -1);
        int cid = 0;
        for (int idx = V - 1; idx >= 0; --idx) {
            int s = order[idx];
            if (comp[s] != -1) continue;
            queue<int> q;
            q.push(s);
            comp[s] = cid;
            while (!q.empty()) {
                int v = q.front(); q.pop();
                for (int to : rg[v]) {
                    if (comp[to] == -1) {
                        comp[to] = cid;
                        q.push(to);
                    }
                }
            }
            cid++;
        }

        assignment.assign(n, 0);
        for (int i = 0; i < n; i++) {
            if (comp[id(i,0)] == comp[id(i,1)]) return false;
            assignment[i] = (comp[id(i,1)] > comp[id(i,0)]) ? 1 : 0;
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

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

    vector<pair<int,int>> edges;
    edges.reserve(M);
    for (int j = 0; j < M; j++) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        edges.push_back({u, v});
    }

    if (M == 0) {
        cout << 0 << "\n";
        cout << string(N, '0') << "\n";
        return 0;
    }

    auto feasible = [&](long long K, const vector<int>* fixedPrefix = nullptr, int prefLen = 0) -> bool {
        TwoSAT sat(N);

        if (fixedPrefix) {
            for (int i = 0; i < prefLen; i++) {
                sat.add_unit(i, (*fixedPrefix)[i] == 1);
            }
        }

        for (auto [u, v] : edges) {
            long long tu[2] = {A[u], A[u] + D[u]};
            long long tv[2] = {A[v], A[v] + D[v]};
            for (int su = 0; su < 2; su++) {
                for (int sv = 0; sv < 2; sv++) {
                    if (llabs(tu[su] - tv[sv]) < K) {
                        // forbid (u=su and v=sv): (!u=su) OR (!v=sv)
                        sat.add_or(u, su ^ 1, v, sv ^ 1);
                    }
                }
            }
        }
        return sat.satisfiable();
    };

    long long lo = 0, hi = 2000000001LL; // [lo, hi)
    while (hi - lo > 1) {
        long long mid = (lo + hi) >> 1;
        if (feasible(mid)) lo = mid;
        else hi = mid;
    }
    long long K = lo;

    vector<int> pref(N, 0);
    for (int i = 0; i < N; i++) {
        pref[i] = 0;
        if (!feasible(K, &pref, i + 1)) {
            pref[i] = 1;
        }
    }

    string S;
    S.reserve(N);
    for (int i = 0; i < N; i++) S.push_back(char('0' + pref[i]));

    cout << K << "\n" << S << "\n";
    return 0;
}

---

この解説は gpt-5.3-codex によって生成されました。