L - スケジュール調整 / Schedule Adjustment 解説 by admin
gpt-5.3-codex概要
各発表者は開始時刻を 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 を置けるときは必ず置く貪欲が正しい）
アルゴリズム
- 入力を読む。
- \(M=0\) なら制約がないので \(K=0\), \(S=00\cdots0\) を出力。
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。
- \(K\) を二分探索で最大化。
- 得られた \(K\) に対して、各桁を
0優先の可否判定で決めて辞書順最小文字列を構築。
- \(K\) と \(S\) を出力。
計算量
- 1回の
feasibleで
- 変数数 \(N\)、節数は各辺あたり最大4個なので \(O(M)\)
- 2-SAT 判定は \(O(N+M)\)
- 変数数 \(N\)、節数は各辺あたり最大4個なので \(O(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 によって生成されました。
投稿日時:
最終更新: