概要 辺の流量に下限があったりする最小費用流を、思いつく範囲で一般化してみました。 記法の定義 を有向グラフとします。 フロー に対して、その境界 を で定義します。 つまり、境界は各頂点から流れ出る量を表しています。 ベクトルに対して不等号を使っ…

概要 この記事の内容は [1] の解説の一部を抜き出して説明したものです。 カタラン数 が と等しいことを、鏡像法 *1 で説明します。 本文 は、グリッド上を右上方向に、 から まで、 を満たすように移動する方法の数と一致します。 の条件を一旦忘れて、 か…

概要 最小カットを用いると、 及び劣モジュラな について \begin{align} \text{Minimize}&\quad \alpha + \sum _ i \theta _ i (x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) \cr \text{subject to}&\quad x \in \lbrace 0, 1 \rbrace ^ n \end{a…

概要 Wavelet Matrix は 2 次元空間の点群に関するクエリを処理するデータ構造と見ることが出来ます。 これを発展させて 3 次元空間の点群に関するクエリを で処理するデータ構造が存在します。 出来ること を非負整数の つ組の列として、データ構造を構築す…

概要 区間 を のそれぞれを軸とする 次元平面にプロットするという方法を紹介します。 図 まず、 つの区間を置いた図がこれです。 赤い点がプロットされた区間であり、斜めの対角線を と思うと で示した部分がその区間に該当します。 点線によって領域が つ…

概要 Monge 性が関係している問題のリストを作ります。 noshi91 は過去問をあまり埋めていないので、貧弱なリストになると思います。 もし載っていないものがあったら教えてもらえると嬉しいです (noshi91 に対するネタバレを気にする必要はありません)。 リ…

概要 No.1467 Selling Cars - yukicoder の非常に雑な解説 解法 を固定して最小費用流にエンコードすると以下のようになります。 頂点の数値は湧き出しの量です。 実際には適切に座標圧縮します。 これは series-parallel graph なので最小費用流が効率的に…

概要 for (auto t: subsets(s)) で s (の bit 列を集合と解釈したとき) の部分集合を走査できるようなライブラリを書きました。 単純には std::vector<int> を返せばいいのですが、速度が少し気になるので、それを解決します。 部分集合に限らず、多次元ループな</int>…

概要 Convex Hull Trick で最小値取得クエリの が整数の時、アルゴリズム内で直線が不要かどうかチェックする部分を簡単に記述することが出来る。 特に、傾きと切片を掛けることでオーバーフローする問題を発生させない。 本文 Convex Hull Trick で、最小値…

概要 が与えられて の構造を観察します。 結論 について、次のうちいずれかが成り立ちます。 証明 とすると、中国剰余定理から 。 を 1 つ固定して考えると、 のとき、 は存在しないか、一意に定まる。 のとき、 の形の条件が付く。 のとき、 は存在しないか…

同じ列にある つの式は、の元で同値です。 次の つの式が成立します。