概要

各発表者は開始時刻を \(2\) 通りから選びます。与えられた \(M\) 組について、開始時刻の差の最小値をできるだけ大きくし、その最大値 \(K\) と、それを達成する辞書順最小の選び方を求めます。

考察

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

• \(X_i=0\) のとき、開始時刻は \(A_i\)
• \(X_i=1\) のとき、開始時刻は \(A_i+D_i\)

とします。

ある値 \(k\) に対して、

すべての指定された組 \((u,v)\) について、開始時刻の差が \(k\) 以上にできるか？

を判定できれば、\(K\) は二分探索で求められます。

なぜなら、ある \(k\) が達成可能なら、それより小さい値も必ず達成可能です。
逆に、ある \(k\) が達成不可能なら、それより大きい値も達成不可能です。

つまり、達成可能性には単調性があります。

---

達成可能性判定は 2-SAT になる

組 \((u,v)\) に注目します。

\(X_u=a\), \(X_v=b\) と選んだときの開始時刻の差を事前に計算しておきます。

もしその差が \(k\) 未満なら、この組み合わせは使えません。

つまり、

\[ X_u=a \land X_v=b \]

は禁止です。

これは次のように書き換えられます。

\[ \neg(X_u=a \land X_v=b) \]

\[ \equiv (X_u \neq a) \lor (X_v \neq b) \]

これは 2-SAT の節です。

例えば、\(X_u=0\), \(X_v=1\) が禁止なら、

\[ (X_u \neq 0) \lor (X_v \neq 1) \]

すなわち、

\[ (X_u=1) \lor (X_v=0) \]

という制約になります。

2-SAT では、節

\[ P \lor Q \]

を次の含意に変換します。

\[ \neg P \Rightarrow Q \]

\[ \neg Q \Rightarrow P \]

今回の場合、禁止条件

\[ (X_u=a) \land (X_v=b) \]

に対して、

\[ (X_u=a) \Rightarrow (X_v \neq b) \]

\[ (X_v=b) \Rightarrow (X_u \neq a) \]

という辺を張ります。

この含意グラフで、ある変数 \(X_i\) について \(X_i=0\) と \(X_i=1\) が同じ強連結成分に入ってしまう場合、矛盾があるため不可能です。

---

辞書順最小の文字列を求める

最大値 \(K\) が分かったあと、辞書順最小の \(S\) を貪欲に決めます。

左から順に見て、各位置 \(i\) についてまず \(S_i=0\) に固定してみます。

• その状態で \(f(S)=K\) を達成可能なら、\(S_i=0\) にする
• 不可能なら、\(S_i=1\) にする

辞書順では 0 が 1 より小さいので、左から順に可能な限り 0 を選ぶことで辞書順最小になります。

固定条件 \(S_i=c\) も 2-SAT に追加できます。
これは単位節 \(X_i=c\) であり、含意グラフでは

\[ X_i \neq c \Rightarrow X_i=c \]

という辺を追加すればよいです。

アルゴリズム

1. 各組 \((u,v)\) について、\(X_u,X_v\) の \(4\) 通りの組み合わせに対する時刻差を事前計算する。
2. ある \(k\) が達成可能かを判定する関数 feasible(k) を用意する。
   • 各組について、時刻差が \(k\) 未満になる選択の組を禁止する。
   • 禁止条件を 2-SAT の含意グラフに変換する。
   • 強連結成分分解を行い、各変数について \(0\) と \(1\) が同じ成分にないか確認する。
3. \(k\) について二分探索し、最大の達成可能値 \(K\) を求める。
4. \(K\) を固定し、左から順に文字列を構築する。
   • まず 0 に固定して 2-SAT 判定する。
   • 可能なら 0、不可能なら 1 にする。
5. \(K\) と得られた文字列を出力する。

計算量

\(C\) を時刻差の最大値の上限とします。ここでは \(C \leq 2 \times 10^9\) です。

1 回の 2-SAT 判定では、頂点数は \(2N\)、辺数は高々 \(O(M+N)\) です。
したがって、1 回の判定は \(O(N+M)\) です。

二分探索で \(O(\log C)\) 回、辞書順最小文字列の構築で \(N\) 回判定を行うので、

• 時間計算量: \(O((N+\log C)(N+M))\)
• 空間計算量: \(O(N+M)\)

実装のポイント

• 各変数 \(X_i\) のリテラルを次のように表しています。

  • \((i \ll 1) | 0\) : \(X_i=0\)
  • \((i \ll 1) | 1\) : \(X_i=1\)

• 反対のリテラルは ^ 1 で得られます。

  • \(X_i=0\) の反対は \(X_i=1\)
  • \(X_i=1\) の反対は \(X_i=0\)

• 時刻は最大で \(2 \times 10^9\) になるため、long long を使うと安全です。

• 2-SAT の判定には強連結成分分解を使います。このコードでは Tarjan のアルゴリズムで実装しています。

  ソースコード

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

struct Constraint {
    int u, v;
    long long diff[2][2];
};

struct TwoSatChecker {
    int n, V;
    vector<Constraint> cons;

    vector<int> head, to, nxt;
    vector<int> disc, low, comp, st;
    vector<unsigned char> in_st;
    int timer, comp_cnt;

    TwoSatChecker(int n_, vector<Constraint>&& cons_)
        : n(n_), V(2 * n_), cons(move(cons_)),
          head(V, -1), disc(V), low(V), comp(V), in_st(V) {
        size_t cap = 8ULL * cons.size() + n + 10;
        to.reserve(cap);
        nxt.reserve(cap);
        st.reserve(V);
    }

    inline void add_edge(int a, int b) {
        nxt.push_back(head[a]);
        to.push_back(b);
        head[a] = (int)to.size() - 1;
    }

    void dfs(int v) {
        disc[v] = low[v] = ++timer;
        st.push_back(v);
        in_st[v] = 1;

        for (int e = head[v]; e != -1; e = nxt[e]) {
            int w = to[e];
            if (!disc[w]) {
                dfs(w);
                low[v] = min(low[v], low[w]);
            } else if (in_st[w]) {
                low[v] = min(low[v], disc[w]);
            }
        }

        if (low[v] == disc[v]) {
            while (true) {
                int w = st.back();
                st.pop_back();
                in_st[w] = 0;
                comp[w] = comp_cnt;
                if (w == v) break;
            }
            comp_cnt++;
        }
    }

    bool feasible(long long k, const vector<int>* fixed = nullptr) {
        fill(head.begin(), head.end(), -1);
        to.clear();
        nxt.clear();

        for (const auto& c : cons) {
            for (int a = 0; a < 2; a++) {
                for (int b = 0; b < 2; b++) {
                    if (c.diff[a][b] < k) {
                        int p = (c.u << 1) | a;
                        int q = (c.v << 1) | b;
                        add_edge(p, q ^ 1);
                        add_edge(q, p ^ 1);
                    }
                }
            }
        }

        if (fixed) {
            for (int i = 0; i < n; i++) {
                if ((*fixed)[i] != -1) {
                    int lit = (i << 1) | (*fixed)[i];
                    add_edge(lit ^ 1, lit);
                }
            }
        }

        fill(disc.begin(), disc.end(), 0);
        fill(comp.begin(), comp.end(), -1);
        fill(in_st.begin(), in_st.end(), 0);
        st.clear();
        timer = 0;
        comp_cnt = 0;

        for (int i = 0; i < V; i++) {
            if (!disc[i]) dfs(i);
        }

        for (int i = 0; i < n; i++) {
            if (comp[i << 1] == comp[(i << 1) | 1]) return false;
        }
        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<Constraint> cons;
    cons.reserve(M);

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;

        Constraint c;
        c.u = u;
        c.v = v;

        for (int a = 0; a < 2; a++) {
            for (int b = 0; b < 2; b++) {
                long long tu = A[u] + (a ? D[u] : 0);
                long long tv = A[v] + (b ? D[v] : 0);
                c.diff[a][b] = abs(tu - tv);
            }
        }

        cons.push_back(c);
    }

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

    TwoSatChecker checker(N, move(cons));

    long long ok = 0, ng = 2000000001LL;
    while (ng - ok > 1) {
        long long mid = (ok + ng) / 2;
        if (checker.feasible(mid)) ok = mid;
        else ng = mid;
    }

    vector<int> fixed(N, -1);
    string ans(N, '0');

    for (int i = 0; i < N; i++) {
        fixed[i] = 0;
        if (checker.feasible(ok, &fixed)) {
            ans[i] = '0';
        } else {
            fixed[i] = 1;
            ans[i] = '1';
        }
    }

    cout << ok << '\n' << ans << '\n';
    return 0;
}

---

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