凸多角形の構成と桁DP：ベクトル選択の数え上げ

凸多角形を構成する際、同一のベクトルは連続して現れる必要があります。この問題は、与えられた $n$ 個のベクトル $(x_i, y_i)$ をそれぞれ $c_i$ 個選択し、閉路を形成しつつ、全ての座標が指定された範囲 $m$ に収まる組み合わせを求める問題に帰着できます。

条件は、正の方向の総和と負の方向の総和が等しく、かつその最大値が $m$ 以下であることです。 $$\sum_{x_i>0} c_ix_i = -\sum_{x_i<0} c_ix_i \le m$$ $y$ 軸方向についても同様の式が成り立ちます。$|x|, |y| \le 4$ と値が小さいため、下位ビットから順に決定していく桁DPが有効です。

状態として、現在のビット位置、各方向（正負、x/y）のキャリー、および $x, y$ が $m$ の境界を超えていないかを持つことで、$O((n\omega)^4 2^n \log m)$ の計算量で解くことができます。

long long memo[32][20][20][20][20][2][2];
int vecX[10], vecY[10];
int N, M;

long long solveDP(int bit, int cpX, int cnX, int cpY, int cnY, bool tightX, bool tightY) {
    if (bit == 30) {
        return (cpX == 0 && cnX == 0 && cpY == 0 && cnY == 0 && tightX && tightY);
    }
    if (memo[bit][cpX][cnX][cpY][cnY][tightX][tightY] != -1) {
        return memo[bit][cpX][cnX][cpY][cnY][tightX][tightY];
    }

    long long count = 0;
    for (int mask = 0; mask < (1 << N); ++mask) {
        int n_cpX = cpX, n_cnX = cnX, n_cpY = cpY, n_cnY = cnY;
        for (int i = 0; i < N; ++i) {
            if ((mask >> i) & 1) {
                if (vecX[i] > 0) n_cpX += vecX[i]; else n_cnX -= vecX[i];
                if (vecY[i] > 0) n_cpY += vecY[i]; else n_cnY -= vecY[i];
            }
        }
        if ((n_cpX % 2 != n_cnX % 2) || (n_cpY % 2 != n_cnY % 2)) continue;

        bool limitX = (M >> bit) & 1;
        bool limitY = (M >> bit) & 1;
        bool nextTightX = limitX ? (n_cpX % 2 == 0 || tightX) : (n_cpX % 2 == 0 && tightX);
        bool nextTightY = limitY ? (n_cpY % 2 == 0 || tightY) : (n_cpY % 2 == 0 && tightY);

        count = (count + solveDP(bit + 1, n_cpX / 2, n_cnX / 2, n_cpY / 2, n_cnY / 2, nextTightX, nextTightY)) % MOD;
    }
    return memo[bit][cpX][cnX][cpY][cnY][tightX][tightY] = count;
}

サボテングラフにおける点削除と連結性の期待値

木構造において、点 $u$ を削除した際に $u, v$ が連結である確率は $\frac{1}{\text{dist}(u,v)}$ となります。これをサボテングラフ（Cactus Graph）に拡張する場合、複数のパスが存在することを考慮しなければなりません。環状の構造が含まれる場合、包含除外原理を用いて連結確率を計算します。

円方木（Round-Square Tree）を構築し、動的計画法を適用します。方点（環に対応するノード）において、環を構成するパスの長さを管理しながら、DPテーブル上で多項式の合成のような遷移を行います。計算量は $O(n^3)$ ですが、各頂点を根として試行することで全ノード間の期待値を集計できます。

void processCactusDP(int u, int p) {
    if (u <= nodeCount) { // 円点
        dp[u][0] = 1;
        for (int v : treeAdj[u]) {
            if (v == p) continue;
            processCactusDP(v, u);
        }
    } else { // 方点
        int root = parent[u];
        // 環上のパスを考慮したDP遷移
        for (int v : ringNodes[u]) {
            if (v == root) continue;
            processCactusDP(v, u);
            int d1 = getDist(v, root), d2 = ringLen[u] - d1;
            // 包含除外：P(A or B) = P(A) + P(B) - P(A and B)
            for (int i = 0; i < nodeCount; ++i) {
                tempDP[i + d1] = (tempDP[i + d1] + dp[v][i]) % MOD;
                tempDP[i + d2] = (tempDP[i + d2] + dp[v][i]) % MOD;
                tempDP[i + d1 + d2 - 1] = (tempDP[i + d1 + d2 - 1] - dp[v][i] + MOD) % MOD;
            }
        }
    }
}

降雨シミュレーションと幾何学的DPのデータ構造最適化

平面上に配置された線分が雨を遮るモデルを考えます。雨滴の挙動は、線分の端点から下方に流れるか、あるいはそのまま垂直に落下するかのいずれかです。この依存関係は走査線法（Scanline）を用いてトポロジカル順序として抽出できます。

最小操作回数を求める際、$f_i$ を位置 $i$ に到達するためのコストとすると、線分の傾きに応じて区間内の $f$ 値が更新されます。この更新操作は「区間加算」と「接尾/接頭辞の最小値取得」を含みます。差分配列 $g_i = f_i - f_{i-1}$ を `std::set` や `std::multiset` で管理し、ポテンシャル解析に基づき、不要になった差分を打ち消し合うことで、全体の計算量を $O(n \log n)$ に抑えることが可能です。

struct Plate {
    int id, x1, y1, x2, y2;
    bool operator<(const Plate& other) const {
        // 現在の走査線位置での上下関係を比較
        double h1 = getY(x_current);
        double h2 = other.getY(x_current);
        return h1 < h2;
    }
};

void updateState(int xL, int xR, bool tiltLeft) {
    if (tiltLeft) {
        auto it = diffPos.lower_bound({xL, -1});
        while (it != diffPos.end() && it->first <= xR) {
            // コストの打ち消し処理と最小値の伝搬
            // ...
        }
    } else {
        // 逆方向の傾斜に対する処理
    }
}