列の隣り合わない $k$ 個の要素を選んだ総和の最大値または最小値の列挙 (other/enumerate-maximum-independent-set-path-sums.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-07-11 16:54:42+09:00
• Include: #include "other/enumerate-maximum-independent-set-path-sums.hpp"

概要

長さ $n$ の列 $a$ について、隣り合わない $k$ 個の添字を選んだときの $a_i$ の総和の最大値または最小値を、全ての $k$ に対して列挙する。

• パス上の重み付き独立集合について、独立集合の大きさごとの最大重みまたは最小重みを求めるものとみなせる。
• 返り値の長さは $\lceil n / 2 \rceil + 1$ である。
• 返り値の $k$ 番目 (0-based indexing) の要素は、maximum が true であれば $k$ 個選んだときの総和の最大値、false であれば $k$ 個選んだときの総和の最小値である。

使い方

enumerate_maximum_independent_set_path_sums<T, bool maximum = true>(a), enumerate_maximum_independent_set_path_sums<bool maximum, T>(a)

• 比較ソートを用いる。
• 引数 $a$ は重みの列である。
• maximum は既定で true であり、true であれば最大値、false であれば最小値を返す。
• 返り値は、 $k$ 個選ぶときの最大値または最小値を $k$ 番目 (0-based indexing) の要素に持つ列である。
• 前提: T は加算、減算、比較が正しく定義されている。
• 前提: アルゴリズム中に現れる加減算結果、および返り値の各要素が T の範囲に収まる。
• 前提: std::is_unsigned_v<T> が false である。

enumerate_maximum_independent_set_path_sums_bucket_sort<T, bool maximum = true>(a), enumerate_maximum_independent_set_path_sums_bucket_sort<bool maximum, T>(a)

• バケットソートを用いる。
• 引数 $a$ は重みの列である。
• maximum は既定で true であり、true であれば最大値、false であれば最小値を返す。
• 返り値は、 $k$ 個選ぶときの最大値または最小値を $k$ 番目 (0-based indexing) の要素に持つ列である。
• 前提: T は bool でない 32 bit 以下のプリミティブな符号付き整数型である。
• 前提: std::is_unsigned_v<T> が false である。
• 前提: 引数として与えられる列は非負整数列である。
• 前提: 引数として与えられる列の総和は T の範囲に収まる。

計算量

• enumerate_maximum_independent_set_path_sums(a): 時間 $O(n \log n)$ 、空間 $O(n)$ 。
• enumerate_maximum_independent_set_path_sums_bucket_sort(a): 列 $a$ の総和を $S$ として時間 $O(n + S)$ 、空間 $O(n + S)$ 。

Verified with

• verify/standalone-enumerate-maximum-independent-set-path-sums.test.cpp
• verify/yukicoder-3322.test.cpp

Code

#ifndef OTHER_ENUMERATE_MAXIMUM_INDEPENDENT_SET_PATH_SUMS_HPP
#define OTHER_ENUMERATE_MAXIMUM_INDEPENDENT_SET_PATH_SUMS_HPP

// 長さ n の列から隣り合わない k 個を選ぶ総和の最大値または最小値を全ての k について求める。
// 符号なし整数型は使用できない。
// 比較ソートによる実装は O(n log n)、バケットソートによる実装は非負整数列の総和を S として O(n + S)。

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

namespace enumerate_maximum_independent_set_path_sums_internal {
template <bool maximum, class T>
bool removable_side(const std::pair<bool, T> &side,
                    const std::pair<bool, T> &center) {
    if (!side.first) {
        return true;
    }
    if (!center.first) {
        return false;
    }
    if constexpr (maximum) {
        return !(center.second < side.second);
    } else {
        return !(side.second < center.second);
    }
}

template <class T, bool maximum>
std::vector<T> marginal_values(const std::vector<T> &a) {
    using P = std::pair<bool, T>;
    const P none(false, T());
    std::vector<P> stack;
    std::vector<T> res;
    stack.reserve(a.size() + 2);
    res.reserve((a.size() + 1) / 2);
    stack.push_back(none);

    const auto add = [&](P x) {
        while (stack.size() >= 2 && stack.back().first &&
               removable_side<maximum>(x, stack.back()) &&
               removable_side<maximum>(stack[stack.size() - 2], stack.back())) {
            P l = std::move(stack[stack.size() - 2]);
            P p = std::move(stack.back());
            x = l.first && x.first ? P(true, l.second - p.second + x.second)
                                   : none;
            res.push_back(std::move(p.second));
            stack.pop_back();
            stack.pop_back();
        }
        stack.push_back(x);
    };

    for (const T &x : a) {
        add(P(true, x));
    }
    add(none);
    return res;
}

// x の絶対値が offset 以下であることを呼び出し元で保証する。
template <class T>
std::size_t bucket_index(const T x, const std::size_t offset) {
    if (T(0) <= x) {
        return offset + static_cast<std::size_t>(x);
    }
    return offset - static_cast<std::size_t>(T(0) - x);
}

template <class T>
T bucket_value(const std::size_t index, const std::size_t offset) {
    if (offset <= index) {
        return static_cast<T>(index - offset);
    }
    return T(0) - static_cast<T>(offset - index);
}
} // namespace enumerate_maximum_independent_set_path_sums_internal

template <class T, bool maximum = true>
std::vector<T>
enumerate_maximum_independent_set_path_sums(const std::vector<T> &a) {
    static_assert(!std::is_unsigned_v<T>,
                  "T must not be an unsigned type in "
                  "enumerate_maximum_independent_set_path_sums.");

    std::vector<T> xs =
        enumerate_maximum_independent_set_path_sums_internal::marginal_values<
            T, maximum>(a);
    std::sort(xs.begin(), xs.end(), [](const T &x, const T &y) {
        if constexpr (maximum) {
            return y < x;
        } else {
            return x < y;
        }
    });
    std::vector<T> res(1, T());
    res.reserve(xs.size() + 1);
    T sum = T();
    for (const T &x : xs) {
        sum += x;
        res.push_back(sum);
    }
    return res;
}

template <bool maximum, class T>
std::vector<T>
enumerate_maximum_independent_set_path_sums(const std::vector<T> &a) {
    return enumerate_maximum_independent_set_path_sums<T, maximum>(a);
}

template <class T, bool maximum = true>
std::vector<T> enumerate_maximum_independent_set_path_sums_bucket_sort(
    const std::vector<T> &a) {
    static_assert(!std::is_unsigned_v<T>,
                  "T must not be an unsigned type in "
                  "enumerate_maximum_independent_set_path_sums_bucket_sort.");
    static_assert(
        std::is_integral_v<T> && std::is_signed_v<T> &&
            !std::is_same_v<T, bool> && sizeof(T) <= sizeof(std::int32_t),
        "T must be a non-bool signed integral type of at most 32 bits in "
        "enumerate_maximum_independent_set_path_sums_bucket_sort.");

    T total = T();
    for (const T &x : a) {
        assert(T(0) <= x);
        assert(x <= std::numeric_limits<T>::max() - total);
        total += x;
    }

    const std::vector<T> xs =
        enumerate_maximum_independent_set_path_sums_internal::marginal_values<
            T, maximum>(a);
    const std::size_t offset = static_cast<std::size_t>(total);
    assert(offset <= (std::numeric_limits<std::size_t>::max() - 1) / 2);
    std::vector<std::size_t> count(offset * 2 + 1, 0);
    for (const T &x : xs) {
        count[enumerate_maximum_independent_set_path_sums_internal::
                  bucket_index(x, offset)] += 1;
    }

    std::vector<T> res(1, T());
    res.reserve(xs.size() + 1);
    T sum = T();
    if constexpr (maximum) {
        for (std::size_t index_plus_one = count.size(); index_plus_one > 0;
             index_plus_one -= 1) {
            const std::size_t index = index_plus_one - 1;
            const std::size_t c = count[index];
            if (c == 0) {
                continue;
            }
            const T x = enumerate_maximum_independent_set_path_sums_internal::
                bucket_value<T>(index, offset);
            for (std::size_t i = 0; i < c; i += 1) {
                sum += x;
                res.push_back(sum);
            }
        }
    } else {
        for (std::size_t index = 0; index < count.size(); index += 1) {
            const std::size_t c = count[index];
            if (c == 0) {
                continue;
            }
            const T x = enumerate_maximum_independent_set_path_sums_internal::
                bucket_value<T>(index, offset);
            for (std::size_t i = 0; i < c; i += 1) {
                sum += x;
                res.push_back(sum);
            }
        }
    }
    return res;
}

template <bool maximum, class T>
std::vector<T> enumerate_maximum_independent_set_path_sums_bucket_sort(
    const std::vector<T> &a) {
    return enumerate_maximum_independent_set_path_sums_bucket_sort<T, maximum>(
        a);
}

#endif

#line 1 "other/enumerate-maximum-independent-set-path-sums.hpp"



// 長さ n の列から隣り合わない k 個を選ぶ総和の最大値または最小値を全ての k について求める。
// 符号なし整数型は使用できない。
// 比較ソートによる実装は O(n log n)、バケットソートによる実装は非負整数列の総和を S として O(n + S)。

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

namespace enumerate_maximum_independent_set_path_sums_internal {
template <bool maximum, class T>
bool removable_side(const std::pair<bool, T> &side,
                    const std::pair<bool, T> &center) {
    if (!side.first) {
        return true;
    }
    if (!center.first) {
        return false;
    }
    if constexpr (maximum) {
        return !(center.second < side.second);
    } else {
        return !(side.second < center.second);
    }
}

template <class T, bool maximum>
std::vector<T> marginal_values(const std::vector<T> &a) {
    using P = std::pair<bool, T>;
    const P none(false, T());
    std::vector<P> stack;
    std::vector<T> res;
    stack.reserve(a.size() + 2);
    res.reserve((a.size() + 1) / 2);
    stack.push_back(none);

    const auto add = [&](P x) {
        while (stack.size() >= 2 && stack.back().first &&
               removable_side<maximum>(x, stack.back()) &&
               removable_side<maximum>(stack[stack.size() - 2], stack.back())) {
            P l = std::move(stack[stack.size() - 2]);
            P p = std::move(stack.back());
            x = l.first && x.first ? P(true, l.second - p.second + x.second)
                                   : none;
            res.push_back(std::move(p.second));
            stack.pop_back();
            stack.pop_back();
        }
        stack.push_back(x);
    };

    for (const T &x : a) {
        add(P(true, x));
    }
    add(none);
    return res;
}

// x の絶対値が offset 以下であることを呼び出し元で保証する。
template <class T>
std::size_t bucket_index(const T x, const std::size_t offset) {
    if (T(0) <= x) {
        return offset + static_cast<std::size_t>(x);
    }
    return offset - static_cast<std::size_t>(T(0) - x);
}

template <class T>
T bucket_value(const std::size_t index, const std::size_t offset) {
    if (offset <= index) {
        return static_cast<T>(index - offset);
    }
    return T(0) - static_cast<T>(offset - index);
}
} // namespace enumerate_maximum_independent_set_path_sums_internal

template <class T, bool maximum = true>
std::vector<T>
enumerate_maximum_independent_set_path_sums(const std::vector<T> &a) {
    static_assert(!std::is_unsigned_v<T>,
                  "T must not be an unsigned type in "
                  "enumerate_maximum_independent_set_path_sums.");

    std::vector<T> xs =
        enumerate_maximum_independent_set_path_sums_internal::marginal_values<
            T, maximum>(a);
    std::sort(xs.begin(), xs.end(), [](const T &x, const T &y) {
        if constexpr (maximum) {
            return y < x;
        } else {
            return x < y;
        }
    });
    std::vector<T> res(1, T());
    res.reserve(xs.size() + 1);
    T sum = T();
    for (const T &x : xs) {
        sum += x;
        res.push_back(sum);
    }
    return res;
}

template <bool maximum, class T>
std::vector<T>
enumerate_maximum_independent_set_path_sums(const std::vector<T> &a) {
    return enumerate_maximum_independent_set_path_sums<T, maximum>(a);
}

template <class T, bool maximum = true>
std::vector<T> enumerate_maximum_independent_set_path_sums_bucket_sort(
    const std::vector<T> &a) {
    static_assert(!std::is_unsigned_v<T>,
                  "T must not be an unsigned type in "
                  "enumerate_maximum_independent_set_path_sums_bucket_sort.");
    static_assert(
        std::is_integral_v<T> && std::is_signed_v<T> &&
            !std::is_same_v<T, bool> && sizeof(T) <= sizeof(std::int32_t),
        "T must be a non-bool signed integral type of at most 32 bits in "
        "enumerate_maximum_independent_set_path_sums_bucket_sort.");

    T total = T();
    for (const T &x : a) {
        assert(T(0) <= x);
        assert(x <= std::numeric_limits<T>::max() - total);
        total += x;
    }

    const std::vector<T> xs =
        enumerate_maximum_independent_set_path_sums_internal::marginal_values<
            T, maximum>(a);
    const std::size_t offset = static_cast<std::size_t>(total);
    assert(offset <= (std::numeric_limits<std::size_t>::max() - 1) / 2);
    std::vector<std::size_t> count(offset * 2 + 1, 0);
    for (const T &x : xs) {
        count[enumerate_maximum_independent_set_path_sums_internal::
                  bucket_index(x, offset)] += 1;
    }

    std::vector<T> res(1, T());
    res.reserve(xs.size() + 1);
    T sum = T();
    if constexpr (maximum) {
        for (std::size_t index_plus_one = count.size(); index_plus_one > 0;
             index_plus_one -= 1) {
            const std::size_t index = index_plus_one - 1;
            const std::size_t c = count[index];
            if (c == 0) {
                continue;
            }
            const T x = enumerate_maximum_independent_set_path_sums_internal::
                bucket_value<T>(index, offset);
            for (std::size_t i = 0; i < c; i += 1) {
                sum += x;
                res.push_back(sum);
            }
        }
    } else {
        for (std::size_t index = 0; index < count.size(); index += 1) {
            const std::size_t c = count[index];
            if (c == 0) {
                continue;
            }
            const T x = enumerate_maximum_independent_set_path_sums_internal::
                bucket_value<T>(index, offset);
            for (std::size_t i = 0; i < c; i += 1) {
                sum += x;
                res.push_back(sum);
            }
        }
    }
    return res;
}

template <bool maximum, class T>
std::vector<T> enumerate_maximum_independent_set_path_sums_bucket_sort(
    const std::vector<T> &a) {
    return enumerate_maximum_independent_set_path_sums_bucket_sort<T, maximum>(
        a);
}

Back to top page