ABC 277 Ex — Constrained Sums

考察

各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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Constrained Sums の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 2-SAT・含意グラフ

主題
  • 2-SAT・含意グラフ: 整数変数をthreshold命題列へ符号化し、単調性と二項制約をimplication graphへ張り、SCCから可否と充足割当を復元できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 2-SAT・含意グラフ

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 2-SAT・含意グラフ

      • 整数変数をthreshold命題列へ符号化し、単調性と二項制約をimplication graphへ張り、SCCから可否と充足割当を復元できる。

      先に読む単元:

      • SCC・縮約DAG・トポロジカル順序 — DAGのtopological processingで得た考え方と実装を再利用し、SCC・縮約DAG・トポロジカル順序の発動条件・正当化・境界を重複なく学ぶ。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題