#1126694 (C++23) No.3306 Life is Easy?

提出ソース
結果

問題	No.3306 Life is Easy?
コンテスト
ユーザー	hitonanode
提出日時	2025-10-07 09:46:59
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	525 ms / 2,000 ms
コード長	17,033 bytes
コンパイル時間	3,415 ms
コンパイル使用メモリ	243,936 KB
実行使用メモリ	21,120 KB
最終ジャッジ日時	2025-10-07 09:47:08
合計ジャッジ時間	8,622 ms
ジャッジサーバーID （参考情報）	judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 35
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <class T1, class T2> T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); }
template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); }
template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); }
template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }
template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }
template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; }

template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec);
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr);
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);

template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; }
template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; }
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; }
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; }
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; }
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }
#ifdef HITONANODE_LOCAL
const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";
#define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl
#define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr)
#else
#define dbg(x) ((void)0)
#define dbgif(cond, x) ((void)0)
#endif

#include <cassert>
#include <queue>
#include <tuple>
#include <vector>

namespace linear_sum_assignment {

template <class T> struct Result {
    T opt;
    std::vector<int> mate;
    std::vector<T> f, g; // dual variables
};

template <class T>
T augment(int nr, int nc, const std::vector<std::vector<T>> &C, std::vector<T> &f, std::vector<T> &g,
          int s, // source row
          std::vector<int> &mate,
          std::vector<int> &mate_inv, // duplicates are allowed (used for k-best algorithms)
          int fixed_rows = 0 // Ignore first rows and corresponding columns (used for k-best algorithms)
) {

    assert(0 <= s and s < nr);
    assert(mate.at(s) < 0);

    static std::vector<T> dist;
    static std::vector<int> prv;
    dist.resize(nc);
    prv.resize(nc);

    std::vector<bool> done(nc);

    for (int i = 0; i < fixed_rows; ++i) {
        if (int j = mate.at(i); j >= 0) done.at(j) = 1;
    }

    {
        int h = 0;
        while (done.at(h)) ++h;

        f.at(s) = C.at(s).at(h) - g.at(h);
        for (int j = h + 1; j < nc; ++j) {
            if (done.at(j)) continue;
            f.at(s) = std::min(f.at(s), C.at(s).at(j) - g.at(j));
        }
    }

    for (int j = 0; j < nc; ++j) {
        if (!done.at(j)) {
            dist.at(j) = C.at(s).at(j) - f.at(s) - g.at(j);
            prv.at(j) = -1;
        }
    }

    int t = -1;
    std::vector<int> stk;

    while (t == -1) {
        int j1 = -1;
        for (int j = 0; j < nc; ++j) {
            if (done.at(j)) continue;
            if (j1 == -1 or dist.at(j) < dist.at(j1) or
                (dist.at(j) == dist.at(j1) and mate_inv.at(j) < 0)) {
                j1 = j;
            }
        }

        if (mate_inv.at(j1) < 0) {
            t = j1;
            break;
        }

        done.at(j1) = 1;
        stk = {j1};

        while (!stk.empty()) {
            const int j2 = stk.back();
            const int i = mate_inv.at(j2);
            if (i < 0) {
                t = stk.back();
                break;
            }
            stk.pop_back();

            for (int j = 0; j < nc; ++j) {
                if (done.at(j)) continue;

                const T len = C.at(i).at(j) - f.at(i) - g.at(j);

                if (dist.at(j) > dist.at(j1) + len) {
                    dist.at(j) = dist.at(j1) + len;
                    prv.at(j) = j2;
                }

                if (len == T()) {
                    stk.push_back(j);
                    done.at(j) = 1;
                }
            }
        }
    }

    const T len = dist.at(t);

    f.at(s) += len;

    for (int i = 0; i < fixed_rows; ++i) {
        if (const int j = mate.at(i); j >= 0) done.at(j) = 0;
    }

    for (int j = 0; j < nc; ++j) {
        if (!done.at(j)) continue;

        g.at(j) -= len - dist.at(j);
    }

    for (int i = fixed_rows; i < nr; ++i) {
        const int j = mate.at(i);
        if (j < 0 or !done.at(j) or j >= nc) continue;
        f.at(i) += len - dist.at(j);
    }

    T ret = T();

    for (int cur = t; cur >= 0;) {
        const int nxt = prv.at(cur);
        if (nxt < 0) {
            mate_inv.at(cur) = s;
            mate.at(s) = cur;
            ret += C.at(s).at(cur);
            break;
        }
        const int i = mate_inv.at(nxt);

        ret += C.at(i).at(cur) - C.at(i).at(nxt);

        mate_inv.at(cur) = i;
        mate.at(i) = cur;
        cur = nxt;
    }

    return ret;
}

// Complexity: O(nr^2 nc)
template <class T> Result<T> _solve(int nr, int nc, const std::vector<std::vector<T>> &C) {

    assert(nr <= nc);

    std::vector<int> mate(nr, -1);
    std::vector<int> mate_inv(nc, -1);
    std::vector<T> f(nr), g(nc); // dual variables, f[i] + g[j] <= C[i][j] holds

    if (nr == 0 or nc == 0) return {T(), mate, f, g};

    if (nr == nc) {
        // Column reduction
        for (int j = nc - 1; j >= 0; --j) {
            g.at(j) = C.at(0).at(j) - f.at(0);
            int imin = 0;
            for (int i = 1; i < nr; ++i) {
                if (g.at(j) > C.at(i).at(j) - f.at(i)) {
                    imin = i;
                    g.at(j) = C.at(i).at(j) - f.at(i);
                }
            }

            if (mate.at(imin) < 0) {
                mate.at(imin) = j;
                mate_inv.at(j) = imin;
            } else if (g.at(j) < g.at(mate.at(imin))) {
                mate_inv.at(mate.at(imin)) = -1;
                mate.at(imin) = j;
                mate_inv.at(j) = imin;
            }
        }

        // Reduction transfer (can be omitted)
        if (nc > 1) {
            for (int i = 0; i < nr; ++i) {
                if (mate.at(i) < 0) continue;
                T best = C.at(i).at(0) - g.at(0), second_best = C.at(i).at(1) - g.at(1);
                int argbest = 0;
                if (best > second_best) std::swap(best, second_best), argbest = 1;

                for (int j = 2; j < nc; ++j) {
                    if (T val = C.at(i).at(j) - g.at(j); val < best) {
                        second_best = best;
                        best = val;
                        argbest = j;
                    } else if (val < second_best) {
                        second_best = val;
                    }
                }

                g.at(argbest) -= second_best - best;
                f.at(i) = second_best;
            }
        }

        // Augmenting row reduction: not implemented
    }

    // Augmentation
    for (int i = 0; i < nr; ++i) {
        if (mate.at(i) < 0) augment(nr, nc, C, f, g, i, mate, mate_inv);
    }

    T ret = 0;
    for (int i = 0; i < nr; ++i) ret += C.at(i).at(mate.at(i));

    return {ret, mate, std::move(f), std::move(g)};
}

// Jonker–Volgenant algorithm: find minimum weight assignment
// Dual problem (nr == nc): maximize sum(f) + sum(g) s.t. f_i + g_j <= C_ij
// Complexity: O(nr nc min(nr, nc))
template <class T> Result<T> solve(int nr, int nc, const std::vector<std::vector<T>> &C) {

    const bool transpose = (nr > nc);

    if (!transpose) return _solve(nr, nc, C);

    std::vector trans(nc, std::vector<T>(nr));

    for (int i = 0; i < nr; ++i) {
        for (int j = 0; j < nc; ++j) trans.at(j).at(i) = C.at(i).at(j);
    }

    auto [v, mate, f, g] = _solve(nc, nr, trans);

    std::vector<int> mate2(nr, -1);
    for (int j = 0; j < nc; ++j) {
        if (mate.at(j) >= 0) mate2.at(mate.at(j)) = j;
    }

    return {v, mate2, g, f};
}

} // namespace linear_sum_assignment

template <class T> struct best_assignments {

    struct Node {
        T opt;
        std::vector<int> mate;
        std::vector<T> f, g; // dual variables
        int fixed_rows;
        std::vector<int> banned_js; // C[fixed_rows][j] が inf となる j の集合

        // for priority queue
        // NOTE: reverse order
        bool operator<(const Node &rhs) const { return opt > rhs.opt; }

        linear_sum_assignment::Result<T> to_output(bool transpose) const {
            if (transpose) {
                std::vector<int> mate2(g.size(), -1);
                for (int i = 0; i < (int)mate.size(); ++i) mate2.at(mate.at(i)) = i;
                return {opt, mate2, g, f};
            } else {
                return {opt, mate, f, g};
            }
        }
    };

    bool transpose;
    int nr_, nc_;
    T inf;
    std::vector<std::vector<T>> C_, Ctmp_;
    std::priority_queue<Node> pq;

    best_assignments(int nr, int nc, const std::vector<std::vector<T>> &C, T inf)
        : transpose(nr > nc), inf(inf) {

        assert((int)C.size() == nr);
        for (int i = 0; i < nr; ++i) assert((int)C.at(i).size() == nc);

        nr_ = transpose ? nc : nr;
        nc_ = transpose ? nr : nc;

        C_.assign(nr_ + (nr_ != nc_), std::vector<T>(nc_, T()));
        for (int i = 0; i < nr; ++i) {
            for (int j = 0; j < nc; ++j) {
                C_.at(transpose ? j : i).at(transpose ? i : j) = C.at(i).at(j);
            }
        }

        Ctmp_ = C_;

        auto [opt, mate, f, g] = linear_sum_assignment::solve(C_.size(), nc, C_);

        pq.emplace(Node{opt, std::move(mate), std::move(f), std::move(g), 0, {}});
    }

    bool finished() const { return pq.empty(); }

    linear_sum_assignment::Result<T> yield() {
        assert(!pq.empty());

        const Node ret = pq.top();
        pq.pop();

        for (int fixed_rows = ret.fixed_rows; fixed_rows < nr_; ++fixed_rows) {
            std::vector<int> banned_js;
            if (fixed_rows == ret.fixed_rows) banned_js = ret.banned_js;

            const int s = fixed_rows;
            banned_js.push_back(ret.mate.at(s));

            if ((int)banned_js.size() >= nc_) continue;

            auto f = ret.f;
            auto g = ret.g;
            auto mate = ret.mate;

            std::vector<int> mate_inv(nc_, nr_);
            for (int i = 0; i < nr_; ++i) mate_inv.at(mate.at(i)) = i;

            std::vector<int> iscoldone(nc_);
            for (int i = 0; i < fixed_rows; ++i) iscoldone.at(mate.at(i)) = 1;

            for (int j : banned_js) Ctmp_.at(s).at(j) = inf;

            mate_inv.at(mate.at(s)) = -1;
            mate.at(s) = -1;

            auto aug = linear_sum_assignment::augment(
                nr_, nc_, Ctmp_, f, g, s, mate, mate_inv, fixed_rows);

            for (int j = 0; j < nc_; ++j) {
                if (mate_inv.at(j) < 0) { // nrows < ncols
                    g.at(j) = -f.back();
                    for (int i = fixed_rows; i < nr_; ++i) {
                        g.at(j) = std::min(g.at(j), Ctmp_.at(i).at(j) - f.at(i));
                    }
                }
            }

            if (Ctmp_.at(s).at(mate.at(s)) < inf) {
                pq.emplace(Node{
                    ret.opt + aug - C_.at(s).at(ret.mate.at(s)),
                    std::move(mate),
                    std::move(f),
                    std::move(g),
                    fixed_rows,
                    banned_js,
                });
            }

            for (int j : banned_js) Ctmp_.at(s).at(j) = C_.at(s).at(j);
        }

        return ret.to_output(transpose);
    }
};


int main() {
    int N, M;
    cin >> N >> M;
    vector A(N, vector<int>(M));
    cin >> A;

    const int K = N / 2;
    vector mat(K, vector<lint>(K));
    REP(i, K) REP(j, K) {
        int best = 0;
        REP(k, M) chmax(best, A.at(N - 1 - j).at(k) - A.at(i).at(k));
        mat.at(i).at(j) = -best;
    }

    auto res = linear_sum_assignment::solve(K, K, mat);
    cout << -res.opt << '\n';
}
yukicoder

結果

ソースコード
