$K$-ary Optimization
(src/optimization/KaryOptimization.hpp)

• View this file on GitHub
• Last update: 2024-06-01 01:35:37+09:00
• Include: #include "src/optimization/KaryOptimization.hpp"

MINIMIZE = false は未 verify につき注意

概要

$[k] := \lbrace 0, 1, \dots , k - 1 \rbrace$ とする． $\alpha \in \mathbb{Z}, \theta _ i \colon [k] \to \mathbb{Z}$ 及び Monge な関数 $\phi _ {i, j} \colon [k] ^ 2 \to \mathbb{Z}$ について，

\[\begin{alignedat}{3} & \mathrm{Minimize} & \quad & \alpha + \sum _ i \theta _ i(x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) \\ & \mathrm{subject\ to} & \quad & x \in [k] ^ n \end{alignedat}\]

を解く． ここで，$0 \le i _ 1 \lt i _ 2 \lt k$ 及び $0 \le j _ 1 \lt j _ 2 \lt k$ を満たす任意の整数の組 $(i _ 1, i _ 2, j _ 1, j _ 2)$ について，$\phi(i _ 1, j _ 1) + \phi(i _ 2, j _ 2) \le \phi(i _ 1, j _ 2) + \phi(i _ 2, j _ 1)$ が成立するとき，$\phi$ は Monge であるという． また，これは $0 \le i \lt k - 1$ 及び $0 \le j \lt k - 1$ を満たす任意の整数の組 $(i, j)$ について，$\phi(i, j) + \phi(i + 1, j + 1) \leq \phi(i, j + 1) + \phi(i + 1, j)$ が成立することと同値である．

出題例

• AtCoder Regular Contest 129 E - Yet Another Minimization
• AtCoder Beginner Contest 347 G - Grid Coloring 2
• AtCoder Beginner Contest 397 G - Maximize Distance

Links

• 最小カット問題の $k$ 値への一般化 - noshi91のメモ

Depends on

• Binary Optimization (Project Selection Problem) (src/optimization/BinaryOptimization.hpp)

Code

#pragma once
#include "BinaryOptimization.hpp"

template <typename T, bool MINIMIZE = true> struct KaryOptimization {
    KaryOptimization() = default;

    KaryOptimization(const std::vector<int>& ks) : n(ks.size()), ks(ks), idx(ks.size()) {
        int cur = 0;
        for (int i = 0; i < n; i++) {
            assert(ks[i] > 0);
            idx[i].resize(ks[i]);
            idx[i][0] = -1;
            for (int d = 1; d < ks[i]; d++) idx[i][d] = cur++;
        }
        bopt = BinaryOptimization<T, MINIMIZE>(cur);
        for (int i = 0; i < n; i++) {
            for (int d = 1; d + 1 < ks[i]; d++) {
                bopt.add_10(idx[i][d], idx[i][d + 1], MINIMIZE ? inf : -inf);
            }
        }
    }

    void add(int i, const std::vector<T>& theta) {
        assert(0 <= i and i < n);
        assert(theta.size() == ks[i]);
        bopt.add(theta.back());
        for (int d = 1; d < ks[i]; d++) bopt.add(idx[i][d], {0, theta[d - 1] - theta[d]});
    }

    void add(int i, int j, std::vector<std::vector<T>> phi) {
        assert(0 <= i and i < n);
        assert(0 <= j and j < n);
        assert(phi.size() == ks[i]);
        std::vector<T> theta_i(ks[i]), theta_j(ks[j]);
        for (int d = 0; d < ks[i]; d++) {
            assert(phi[d].size() == ks[j]);
            theta_i[d] = phi[d][0];
            for (int e = 0; e < ks[j]; e++) phi[d][e] -= theta_i[d];
        }
        for (int e = 0; e < ks[j]; e++) {
            theta_j[e] = phi[0][e];
            for (int d = 0; d < ks[i]; d++) phi[d][e] -= theta_j[e];
        }
        add(i, theta_i);
        add(j, theta_j);
        for (int d = 1; d < ks[i]; d++) {
            for (int e = 1; e < ks[j]; e++) {
                T x = (phi[d][e] + phi[d - 1][e - 1]) - (phi[d][e - 1] + phi[d - 1][e]);
                assert(x <= 0);
                bopt.add(idx[i][d], idx[j][e], {x, 0, 0, 0});
            }
        }
    }

    std::pair<T, std::vector<int>> solve() {
        auto [ans, xs] = bopt.solve();
        std::vector<int> x(n, 0);
        for (int i = 0; i < n; i++) {
            for (int d = 1; d < ks[i]; d++) {
                x[i] += not xs[idx[i][d]];
            }
        }
        return {ans, x};
    }

  private:
    static constexpr T inf = std::numeric_limits<T>::max() / 2;
    int n;
    std::vector<int> ks;
    std::vector<std::vector<int>> idx;
    BinaryOptimization<T, MINIMIZE> bopt;
};

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/maxflow.hpp: line -1: no such header

Back to top page