考察
各X_iは0,…,Mの小さな整数だが、Q個のsum区間制約がcycleを作るため、変数順に決める単純DPにはならない。 threshold命題P_{i,j}: j≤X_iを導入すると、整数値1個がjに関してtrueからfalseへ一度だけ切り替わるboolean列になる。 L≤X_A+X_Bは全整数tについて P_{A,t}∨P_{B,L-t+1}、X_A+X_B≤Rは ¬P_{A,t}∨¬P_{B,R-t+1} と同値になる。 P_{i,0}=true、P_{i,M+1}=false、P_{i,j}⇒P_{i,j-1}を加えると、satisfying assignmentから最大true thresholdをX_iとして復元できる。
採用する候補: 各threshold P_{i,j}を2-SAT変数にし、上下界のsum条件を全tに対する2-literal clauseへ変換してSCCで解く。
M≤100によりNM変数を持て、二変数和の整数不等式をthreshold ORへ正確に線形化できる。
棄却する候補: 各X_iのM+1候補を頂点にした一般CSPをbacktrackingする。
constraint graphに木構造の保証がなく、候補割当ては指数的になる。
iごとにthreshold 0,…,M+1を用意し、端のunit clauseと単調clauseを張る。各queryと関連tについてlower/upperの2-SAT clauseを追加し、implication graphのSCCで矛盾を判定する。可解なら各iの最大true jを出力する。
典型の発動条件
threshold boolean化
発動条件: 小範囲整数変数への大小・和不等式をboolean制約へ落としたいとき。
j≤Xという単調命題列を作り、値をtrue prefixの長さとして表す。
2-SAT
発動条件: 各制約が二つのboolean literalのORへ表せ、全体の可解性と一解が必要なとき。
clauseを2本のimplicationへし、literalと否定が同SCCか調べる。
問題固有の要素
二変数和のlower/upper boundは、全cut位置tで『片方がcutを越える』というORの族に変換できる。
別の問題へ持ち帰る視点: 整数和制約では閾値を一方へ配分するcutを全列挙し、forbiddenな同時閾値を二項clauseにできないか考える。
正当性
threshold列の単調性と端固定で各boolean割当は一整数に対応する。和下限・上限は全thresholdでのORclauseへ同値変換できるため2-SAT可解性と元整数制約可解性が一致。矛盾SCCがなければ最大true thresholdを復元する。
実装上の注意
- threshold indexが0未満なら常true、M+1超なら常falseとしてclauseを簡約し、配列外参照を避ける。
- A_i=B_iのqueryでも同じ変数のliteralを正しく簡約し、復元後に全sum制約を再検査すると安全である。
復習の核
- L=5のlower boundでt=X_A+1を選ぶ反証と、true thresholdがprefixになる単調clauseを小さなMで確認する。
計算量と制約
時間
N整数変数、上限M、Q和制約。threshold変数O(NM)、clause O((N+Q)M)、SCCで同時間。
空間
implication graph O((N+Q)M)。
制約との対応
公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10000; 1 \leq M \leq 100; 1 \leq Q \leq 10000; 1 \leq A_i, B_i \leq N; 0 \leq L_i \leq R_i \leq 2 \times M; All values in the input are integers.
出典