牛ゲー

この組合せで適切かどうか分からないが，こう作った． ライブラリソース 解ける問題 Bellman-Ford アルゴリズム 重み付き有向グラフで，特定の点からすべての点への距離 (パスの重みの和の最小値) を求める． 重みは負でも良い．負閉路があると距離が定義できない ($-\infty$ になる) が，このアルゴリズムはその検出ができる． 計算量は，頂点数 $N$，辺数 $M$ として，$O(NM)$． 牛ゲー 次の制約問題を解く． 変数 $x_i$ ($i = 1, \ldots, n$) に関し，次の制約の下で，$x_n - x_1$ の最大値 (または最小値) を求めよ． $x_{A_j} - x_{B_j} \leq C_j$ $\quad(j = 1, \ldots, m)$ $C_j$ は負でも良い．移項すれば良いので，$x_{A_j} - x_{B_j} \geq C_j$ という制約でも良い． この問題で，求める最大値は，「重み $C_j$ の有向辺 $(B_j, A_j)$ を持つグラフで，$1$ から $N$ への距離」になる (参考リンク )． 次が対応する． 制約を満たせないことと，グラフが負閉路を持つこと いくらでも大きな値を取れることと，グラフで$1$から$N$に到達できないこと 最小値バージョンは，同じ制約の下で $x_1 - x_n$ の最大値を求めて符号を反転すれば良い． 注意: このライブラリでは，Bellman-Ford を用いるので，変数の数$N$，制約の数$M$に対して， $\Omega(NM)$ 時間かかる．制約によっては，(適当な変換をして) ダイクストラなどの 速いアルゴリズムを使う必要があるかもしれない．...

問題概要 問題へのリンク 整数 $N$，$M$ と列$L$，$R$，$S$ が与えられる． $M$個の制約 $$\sum\{ A_j \mid j = L_i, \dots, R_i \} = S_i$$ を満たす長さ $N$ の正の整数の列 $A$ が存在するかどうか判定し， 存在する場合には $A$ の総和の最小値を求めよ． 制約 $1 \leq N, M \leq 4000$，$1 \leq S_i \leq 10^9$ 解 公式解説 略解．click to open 牛ゲー．累積和 $B_i := \sum\{A_j \mid 0 \leq j < i\}$ に関して，次を解けば良い． 次の条件の下で，$B_{N + 1} - B_{1}$ を最小化する $B_{i + 1} - B_i \geq 1$ $B_{R_{i} + 1} - B_{L_i} \geq S_i$ $B_{R_{i} + 1} - B_{L_i} \leq S_i$

「牛ゲー」なる手法のまとめです

公式解説とは違う (より効率の悪い) 方法で解きました．