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

• View this file on GitHub
• Last update: 2026-07-11 16:54:42+09:00

Depends on

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

Code

// competitive-verifier: STANDALONE

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <vector>

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

template <class T, bool maximum = true>
std::vector<T> brute_force(const std::vector<T> &a) {
    const std::size_t n = a.size();
    const std::size_t m = (n + 1) / 2;
    std::vector<T> answer(m + 1, T());
    std::vector<bool> found(m + 1, false);
    const std::uint64_t masks = std::uint64_t{1} << n;
    for (std::uint64_t mask = 0; mask < masks; mask += 1) {
        bool ok = true;
        std::size_t count = 0;
        T sum = T();
        for (std::size_t i = 0; i < n; i += 1) {
            if (((mask / (std::uint64_t{1} << i)) % 2) != 0) {
                if (i > 0 &&
                    ((mask / (std::uint64_t{1} << (i - 1))) % 2) != 0) {
                    ok = false;
                }
                count += 1;
                sum += a[i];
            }
        }
        if (ok && !found[count]) {
            answer[count] = sum;
            found[count] = true;
        } else if (ok) {
            if constexpr (maximum) {
                if (answer[count] < sum) {
                    answer[count] = sum;
                }
            } else {
                if (sum < answer[count]) {
                    answer[count] = sum;
                }
            }
        }
    }
    for (std::size_t i = 0; i <= m; i += 1) {
        assert(found[i]);
    }
    return answer;
}

void test_signed_exhaustive() {
    for (std::size_t n = 0; n <= 6; n += 1) {
        std::vector<long long> a(n);
        auto dfs = [&](auto self, const std::size_t i) -> void {
            if (i == n) {
                const std::vector<long long> expected = brute_force(a);
                const std::vector<long long> expected_min =
                    brute_force<long long, false>(a);
                assert(enumerate_maximum_independent_set_path_sums(a) ==
                       expected);
                assert((enumerate_maximum_independent_set_path_sums<long long,
                                                                    false>(a) ==
                        expected_min));
                assert(enumerate_maximum_independent_set_path_sums<false>(a) ==
                       expected_min);
                return;
            }
            for (long long x = -3; x <= 3; x += 1) {
                a[i] = x;
                self(self, i + 1);
            }
        };
        dfs(dfs, 0);
    }
}

void test_small_signed_type_exhaustive() {
    for (std::size_t n = 0; n <= 6; n += 1) {
        std::vector<signed char> a(n);
        auto dfs = [&](auto self, const std::size_t i) -> void {
            if (i == n) {
                const std::vector<signed char> expected = brute_force(a);
                const std::vector<signed char> expected_min =
                    brute_force<signed char, false>(a);
                assert(enumerate_maximum_independent_set_path_sums(a) ==
                       expected);
                assert((enumerate_maximum_independent_set_path_sums<signed char,
                                                                    false>(a) ==
                        expected_min));
                return;
            }
            for (signed char x = -3; x <= 3;
                 x = static_cast<signed char>(x + 1)) {
                a[i] = x;
                self(self, i + 1);
            }
        };
        dfs(dfs, 0);
    }
}

void test_signed_bucket_sort() {
    for (std::size_t n = 0; n <= 7; n += 1) {
        std::vector<int> a(n);
        auto dfs = [&](auto self, const std::size_t i) -> void {
            if (i == n) {
                const std::vector<int> expected = brute_force(a);
                const std::vector<int> expected_min =
                    brute_force<int, false>(a);
                assert(enumerate_maximum_independent_set_path_sums_bucket_sort(
                           a) == expected);
                assert((enumerate_maximum_independent_set_path_sums_bucket_sort<
                            int, false>(a) == expected_min));
                assert(enumerate_maximum_independent_set_path_sums_bucket_sort<
                           false>(a) == expected_min);
                return;
            }
            for (int x = 0; x <= 4; x += 1) {
                a[i] = x;
                self(self, i + 1);
            }
        };
        dfs(dfs, 0);
    }
}

void test_bucket_large_values() {
    const std::vector<int> a = {100, 1, 100, 1, 100, 1, 100};
    const std::vector<int> expected = brute_force(a);
    const std::vector<int> expected_min = brute_force<int, false>(a);
    assert(enumerate_maximum_independent_set_path_sums(a) == expected);
    assert((enumerate_maximum_independent_set_path_sums<int, false>(a) ==
            expected_min));
    assert(enumerate_maximum_independent_set_path_sums_bucket_sort(a) ==
           expected);
    assert((enumerate_maximum_independent_set_path_sums_bucket_sort<int, false>(
                a) == expected_min));

    const std::vector<std::int32_t> b = {3, 0, 5, 0, 4, 1};
    const std::vector<std::int32_t> expected_b = brute_force(b);
    const std::vector<std::int32_t> expected_b_min =
        brute_force<std::int32_t, false>(b);
    assert(enumerate_maximum_independent_set_path_sums_bucket_sort(b) ==
           expected_b);
    assert((enumerate_maximum_independent_set_path_sums_bucket_sort<
                std::int32_t, false>(b) == expected_b_min));
}

void test_bucket_small_signed_types() {
    const std::vector<short> a = {2, 0, 3, 1, 4};
    const std::vector<short> expected = brute_force(a);
    const std::vector<short> expected_min = brute_force<short, false>(a);
    assert(enumerate_maximum_independent_set_path_sums_bucket_sort(a) ==
           expected);
    assert(
        (enumerate_maximum_independent_set_path_sums_bucket_sort<short, false>(
             a) == expected_min));

    const std::vector<signed char> b = {2, 0, 3, 1, 4};
    const std::vector<signed char> expected_b = brute_force(b);
    const std::vector<signed char> expected_b_min =
        brute_force<signed char, false>(b);
    assert(enumerate_maximum_independent_set_path_sums_bucket_sort(b) ==
           expected_b);
    assert((enumerate_maximum_independent_set_path_sums_bucket_sort<signed char,
                                                                    false>(b) ==
            expected_b_min));
}

struct TestNumber {
    long long value;

    TestNumber() : value(0) {}

    explicit TestNumber(const long long value_) : value(value_) {}

    TestNumber operator+(const TestNumber &other) const {
        return TestNumber(value + other.value);
    }

    TestNumber operator-(const TestNumber &other) const {
        return TestNumber(value - other.value);
    }

    TestNumber &operator+=(const TestNumber &other) {
        value += other.value;
        return *this;
    }

    bool operator<(const TestNumber &other) const {
        return value < other.value;
    }

    bool operator==(const TestNumber &other) const {
        return value == other.value;
    }
};

void test_custom_type() {
    const std::vector<TestNumber> a = {TestNumber(1), TestNumber(100),
                                       TestNumber(1), TestNumber(4),
                                       TestNumber(5)};
    assert(enumerate_maximum_independent_set_path_sums(a) == brute_force(a));
    assert((enumerate_maximum_independent_set_path_sums<TestNumber, false>(a) ==
            brute_force<TestNumber, false>(a)));
}

void test_floating_point() {
    const std::vector<double> a = {1.5, 100.25, 1.5, -3.0, 10.0, 2.0};
    assert(enumerate_maximum_independent_set_path_sums(a) == brute_force(a));
    assert((enumerate_maximum_independent_set_path_sums<double, false>(a) ==
            brute_force<double, false>(a)));
}

void test_type_traits() {
    static_assert(!std::is_unsigned_v<int>,
                  "std::is_unsigned_v<int> must be false in this verify.");
    static_assert(!std::is_unsigned_v<double>,
                  "std::is_unsigned_v<double> must be false in this verify.");
    static_assert(
        !std::is_unsigned_v<TestNumber>,
        "std::is_unsigned_v<TestNumber> must be false in this verify.");
    static_assert(
        std::is_unsigned_v<unsigned int>,
        "std::is_unsigned_v<unsigned int> must be true in this verify.");
}

int main() {
    test_signed_exhaustive();
    test_small_signed_type_exhaustive();
    test_signed_bucket_sort();
    test_bucket_large_values();
    test_bucket_small_signed_types();
    test_custom_type();
    test_floating_point();
    test_type_traits();

    return 0;
}

#line 1 "verify/standalone-enumerate-maximum-independent-set-path-sums.test.cpp"
// competitive-verifier: STANDALONE

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <vector>

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



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

#include <algorithm>
#line 12 "other/enumerate-maximum-independent-set-path-sums.hpp"
#include <limits>
#line 14 "other/enumerate-maximum-independent-set-path-sums.hpp"
#include <utility>
#line 16 "other/enumerate-maximum-independent-set-path-sums.hpp"

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);
}


#line 10 "verify/standalone-enumerate-maximum-independent-set-path-sums.test.cpp"

template <class T, bool maximum = true>
std::vector<T> brute_force(const std::vector<T> &a) {
    const std::size_t n = a.size();
    const std::size_t m = (n + 1) / 2;
    std::vector<T> answer(m + 1, T());
    std::vector<bool> found(m + 1, false);
    const std::uint64_t masks = std::uint64_t{1} << n;
    for (std::uint64_t mask = 0; mask < masks; mask += 1) {
        bool ok = true;
        std::size_t count = 0;
        T sum = T();
        for (std::size_t i = 0; i < n; i += 1) {
            if (((mask / (std::uint64_t{1} << i)) % 2) != 0) {
                if (i > 0 &&
                    ((mask / (std::uint64_t{1} << (i - 1))) % 2) != 0) {
                    ok = false;
                }
                count += 1;
                sum += a[i];
            }
        }
        if (ok && !found[count]) {
            answer[count] = sum;
            found[count] = true;
        } else if (ok) {
            if constexpr (maximum) {
                if (answer[count] < sum) {
                    answer[count] = sum;
                }
            } else {
                if (sum < answer[count]) {
                    answer[count] = sum;
                }
            }
        }
    }
    for (std::size_t i = 0; i <= m; i += 1) {
        assert(found[i]);
    }
    return answer;
}

void test_signed_exhaustive() {
    for (std::size_t n = 0; n <= 6; n += 1) {
        std::vector<long long> a(n);
        auto dfs = [&](auto self, const std::size_t i) -> void {
            if (i == n) {
                const std::vector<long long> expected = brute_force(a);
                const std::vector<long long> expected_min =
                    brute_force<long long, false>(a);
                assert(enumerate_maximum_independent_set_path_sums(a) ==
                       expected);
                assert((enumerate_maximum_independent_set_path_sums<long long,
                                                                    false>(a) ==
                        expected_min));
                assert(enumerate_maximum_independent_set_path_sums<false>(a) ==
                       expected_min);
                return;
            }
            for (long long x = -3; x <= 3; x += 1) {
                a[i] = x;
                self(self, i + 1);
            }
        };
        dfs(dfs, 0);
    }
}

void test_small_signed_type_exhaustive() {
    for (std::size_t n = 0; n <= 6; n += 1) {
        std::vector<signed char> a(n);
        auto dfs = [&](auto self, const std::size_t i) -> void {
            if (i == n) {
                const std::vector<signed char> expected = brute_force(a);
                const std::vector<signed char> expected_min =
                    brute_force<signed char, false>(a);
                assert(enumerate_maximum_independent_set_path_sums(a) ==
                       expected);
                assert((enumerate_maximum_independent_set_path_sums<signed char,
                                                                    false>(a) ==
                        expected_min));
                return;
            }
            for (signed char x = -3; x <= 3;
                 x = static_cast<signed char>(x + 1)) {
                a[i] = x;
                self(self, i + 1);
            }
        };
        dfs(dfs, 0);
    }
}

void test_signed_bucket_sort() {
    for (std::size_t n = 0; n <= 7; n += 1) {
        std::vector<int> a(n);
        auto dfs = [&](auto self, const std::size_t i) -> void {
            if (i == n) {
                const std::vector<int> expected = brute_force(a);
                const std::vector<int> expected_min =
                    brute_force<int, false>(a);
                assert(enumerate_maximum_independent_set_path_sums_bucket_sort(
                           a) == expected);
                assert((enumerate_maximum_independent_set_path_sums_bucket_sort<
                            int, false>(a) == expected_min));
                assert(enumerate_maximum_independent_set_path_sums_bucket_sort<
                           false>(a) == expected_min);
                return;
            }
            for (int x = 0; x <= 4; x += 1) {
                a[i] = x;
                self(self, i + 1);
            }
        };
        dfs(dfs, 0);
    }
}

void test_bucket_large_values() {
    const std::vector<int> a = {100, 1, 100, 1, 100, 1, 100};
    const std::vector<int> expected = brute_force(a);
    const std::vector<int> expected_min = brute_force<int, false>(a);
    assert(enumerate_maximum_independent_set_path_sums(a) == expected);
    assert((enumerate_maximum_independent_set_path_sums<int, false>(a) ==
            expected_min));
    assert(enumerate_maximum_independent_set_path_sums_bucket_sort(a) ==
           expected);
    assert((enumerate_maximum_independent_set_path_sums_bucket_sort<int, false>(
                a) == expected_min));

    const std::vector<std::int32_t> b = {3, 0, 5, 0, 4, 1};
    const std::vector<std::int32_t> expected_b = brute_force(b);
    const std::vector<std::int32_t> expected_b_min =
        brute_force<std::int32_t, false>(b);
    assert(enumerate_maximum_independent_set_path_sums_bucket_sort(b) ==
           expected_b);
    assert((enumerate_maximum_independent_set_path_sums_bucket_sort<
                std::int32_t, false>(b) == expected_b_min));
}

void test_bucket_small_signed_types() {
    const std::vector<short> a = {2, 0, 3, 1, 4};
    const std::vector<short> expected = brute_force(a);
    const std::vector<short> expected_min = brute_force<short, false>(a);
    assert(enumerate_maximum_independent_set_path_sums_bucket_sort(a) ==
           expected);
    assert(
        (enumerate_maximum_independent_set_path_sums_bucket_sort<short, false>(
             a) == expected_min));

    const std::vector<signed char> b = {2, 0, 3, 1, 4};
    const std::vector<signed char> expected_b = brute_force(b);
    const std::vector<signed char> expected_b_min =
        brute_force<signed char, false>(b);
    assert(enumerate_maximum_independent_set_path_sums_bucket_sort(b) ==
           expected_b);
    assert((enumerate_maximum_independent_set_path_sums_bucket_sort<signed char,
                                                                    false>(b) ==
            expected_b_min));
}

struct TestNumber {
    long long value;

    TestNumber() : value(0) {}

    explicit TestNumber(const long long value_) : value(value_) {}

    TestNumber operator+(const TestNumber &other) const {
        return TestNumber(value + other.value);
    }

    TestNumber operator-(const TestNumber &other) const {
        return TestNumber(value - other.value);
    }

    TestNumber &operator+=(const TestNumber &other) {
        value += other.value;
        return *this;
    }

    bool operator<(const TestNumber &other) const {
        return value < other.value;
    }

    bool operator==(const TestNumber &other) const {
        return value == other.value;
    }
};

void test_custom_type() {
    const std::vector<TestNumber> a = {TestNumber(1), TestNumber(100),
                                       TestNumber(1), TestNumber(4),
                                       TestNumber(5)};
    assert(enumerate_maximum_independent_set_path_sums(a) == brute_force(a));
    assert((enumerate_maximum_independent_set_path_sums<TestNumber, false>(a) ==
            brute_force<TestNumber, false>(a)));
}

void test_floating_point() {
    const std::vector<double> a = {1.5, 100.25, 1.5, -3.0, 10.0, 2.0};
    assert(enumerate_maximum_independent_set_path_sums(a) == brute_force(a));
    assert((enumerate_maximum_independent_set_path_sums<double, false>(a) ==
            brute_force<double, false>(a)));
}

void test_type_traits() {
    static_assert(!std::is_unsigned_v<int>,
                  "std::is_unsigned_v<int> must be false in this verify.");
    static_assert(!std::is_unsigned_v<double>,
                  "std::is_unsigned_v<double> must be false in this verify.");
    static_assert(
        !std::is_unsigned_v<TestNumber>,
        "std::is_unsigned_v<TestNumber> must be false in this verify.");
    static_assert(
        std::is_unsigned_v<unsigned int>,
        "std::is_unsigned_v<unsigned int> must be true in this verify.");
}

int main() {
    test_signed_exhaustive();
    test_small_signed_type_exhaustive();
    test_signed_bucket_sort();
    test_bucket_large_values();
    test_bucket_small_signed_types();
    test_custom_type();
    test_floating_point();
    test_type_traits();

    return 0;
}

Back to top page