verify/standalone-minimum-mod-range-increment-decrement-operations.test.cpp

• View this file on GitHub
• Last update: 2026-05-29 20:48:10+09:00

Depends on

• 区間インクリメント/デクリメントの最小回数（$\text{mod }m$） (other/minimum-mod-range-increment-decrement-operations.hpp)

Code

// competitive-verifier: STANDALONE

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

#include "../other/minimum-mod-range-increment-decrement-operations.hpp"

namespace {
int encode(const std::vector<int> &values, int mod) {
    int state = 0;
    int base = 1;
    for (int x : values) {
        state += x * base;
        base *= mod;
    }
    return state;
}

std::vector<int> decode(int state, int n, int mod) {
    std::vector<int> values(n);
    for (int i = 0; i < n; ++i) {
        values[i] = state % mod;
        state /= mod;
    }
    return values;
}

std::vector<int> all_distances(int n, int mod) {
    int total = 1;
    for (int i = 0; i < n; ++i) {
        total *= mod;
    }

    std::vector<int> dist(total, -1);
    std::queue<int> q;
    dist[0] = 0;
    q.push(0);

    while (!q.empty()) {
        const int state = q.front();
        q.pop();

        const auto values = decode(state, n, mod);
        for (int l = 0; l < n; ++l) {
            for (int r = l; r < n; ++r) {
                for (int delta : {-1, 1}) {
                    auto next = values;
                    for (int i = l; i <= r; ++i) {
                        next[i] += delta;
                        if (next[i] == mod) {
                            next[i] = 0;
                        }
                        if (next[i] < 0) {
                            next[i] += mod;
                        }
                    }
                    const int next_state = encode(next, mod);
                    if (dist[next_state] != -1) {
                        continue;
                    }
                    dist[next_state] = dist[state] + 1;
                    q.push(next_state);
                }
            }
        }
    }

    return dist;
}

long long mod_difference_ll(long long from, long long to, long long mod) {
    return from <= to ? to - from : to + mod - from;
}

void self_test() {
    for (int n = 1; n <= 4; ++n) {
        for (int mod = 1; mod <= 3; ++mod) {
            int total = 1;
            for (int i = 0; i < n; ++i) {
                total *= mod;
            }

            const auto dist = all_distances(n, mod);
            for (int a_state = 0; a_state < total; ++a_state) {
                const auto a_values = decode(a_state, n, mod);
                std::vector<long long> a(n);
                for (int i = 0; i < n; ++i) {
                    a[i] = a_values[i];
                }

                for (int b_state = 0; b_state < total; ++b_state) {
                    const auto b_values = decode(b_state, n, mod);
                    std::vector<long long> b(n);
                    std::vector<int> delta_values(n);
                    for (int i = 0; i < n; ++i) {
                        b[i] = b_values[i];
                        delta_values[i] = static_cast<int>(
                            mod_difference_ll(a[i], b[i], mod));
                    }
                    assert(minimum_mod_range_increment_decrement_operations(
                               a, b, static_cast<long long>(mod)) ==
                           dist[encode(delta_values, mod)]);
                }
            }
        }
    }

    for (int mod = 1; mod <= 4; ++mod) {
        const int n = 5;
        int total = 1;
        for (int i = 0; i < n; ++i) {
            total *= mod;
        }

        const auto dist = all_distances(n, mod);
        std::vector<long long> a(n, 0);
        for (int b_state = 0; b_state < total; ++b_state) {
            const auto b_values = decode(b_state, n, mod);
            std::vector<long long> b(n);
            for (int i = 0; i < n; ++i) {
                b[i] = b_values[i];
            }
            assert(minimum_mod_range_increment_decrement_operations(
                       a, b, static_cast<long long>(mod)) == dist[b_state]);
        }
    }
}
} // namespace

int main() {
    self_test();
    return 0;
}

#line 1 "verify/standalone-minimum-mod-range-increment-decrement-operations.test.cpp"
// competitive-verifier: STANDALONE

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

#line 1 "other/minimum-mod-range-increment-decrement-operations.hpp"



// 数列を mod m 上で見たとき、区間に +1 または -1 を加える操作の最小回数を求める。
// 区間に整数 x を加える操作の最小 sum |x| と同値である。
// a, b は同じ長さで、各要素は [0, m) を仮定する。
// T は 64 bit 整数型、m <= 10^9 を想定する。
// 計算量 O(N log N)。

#include <algorithm>
#line 12 "other/minimum-mod-range-increment-decrement-operations.hpp"
#include <cstddef>
#include <type_traits>
#line 15 "other/minimum-mod-range-increment-decrement-operations.hpp"

template <class T>
T minimum_mod_range_increment_decrement_operations(std::vector<T> a,
                                                   std::vector<T> b, T m) {
    static_assert(std::is_integral_v<T>, "T must be integer.");
    static_assert(sizeof(T) >= sizeof(long long),
                  "T must be at least 64-bit integer type.");

    assert(a.size() == b.size());
    assert(m > 0);

    const std::size_t n = a.size();
    std::vector<T> differences;
    differences.reserve(n + 1);

    auto mod_difference = [m](T from, T to) -> T {
        return from <= to ? to - from : m - (from - to);
    };

    auto add_mod_difference = [m](std::size_t &quotient, T &remainder, T diff) {
        if (remainder >= m - diff) {
            remainder -= m - diff;
            ++quotient;
        } else {
            remainder += diff;
        }
    };

    T previous = 0;
    std::size_t negative_count = 0;
    T remainder = 0;
    for (std::size_t i = 0; i < n; ++i) {
        if constexpr (std::is_signed_v<T>) {
            assert(0 <= a[i]);
            assert(0 <= b[i]);
        }
        assert(a[i] < m);
        assert(b[i] < m);

        const T current = mod_difference(a[i], b[i]);
        const T diff = mod_difference(previous, current);
        differences.emplace_back(diff);
        add_mod_difference(negative_count, remainder, diff);
        previous = current;
    }

    const T last = mod_difference(previous, T(0));
    differences.emplace_back(last);
    add_mod_difference(negative_count, remainder, last);

    assert(remainder == 0);
    assert(negative_count <= n + 1);

    std::sort(differences.begin(), differences.end());

    const std::size_t keep_count = n + 1 - negative_count;
    T answer = 0;
    for (std::size_t i = 0; i < keep_count; ++i) {
        answer += differences[i];
    }
    return answer;
}


#line 8 "verify/standalone-minimum-mod-range-increment-decrement-operations.test.cpp"

namespace {
int encode(const std::vector<int> &values, int mod) {
    int state = 0;
    int base = 1;
    for (int x : values) {
        state += x * base;
        base *= mod;
    }
    return state;
}

std::vector<int> decode(int state, int n, int mod) {
    std::vector<int> values(n);
    for (int i = 0; i < n; ++i) {
        values[i] = state % mod;
        state /= mod;
    }
    return values;
}

std::vector<int> all_distances(int n, int mod) {
    int total = 1;
    for (int i = 0; i < n; ++i) {
        total *= mod;
    }

    std::vector<int> dist(total, -1);
    std::queue<int> q;
    dist[0] = 0;
    q.push(0);

    while (!q.empty()) {
        const int state = q.front();
        q.pop();

        const auto values = decode(state, n, mod);
        for (int l = 0; l < n; ++l) {
            for (int r = l; r < n; ++r) {
                for (int delta : {-1, 1}) {
                    auto next = values;
                    for (int i = l; i <= r; ++i) {
                        next[i] += delta;
                        if (next[i] == mod) {
                            next[i] = 0;
                        }
                        if (next[i] < 0) {
                            next[i] += mod;
                        }
                    }
                    const int next_state = encode(next, mod);
                    if (dist[next_state] != -1) {
                        continue;
                    }
                    dist[next_state] = dist[state] + 1;
                    q.push(next_state);
                }
            }
        }
    }

    return dist;
}

long long mod_difference_ll(long long from, long long to, long long mod) {
    return from <= to ? to - from : to + mod - from;
}

void self_test() {
    for (int n = 1; n <= 4; ++n) {
        for (int mod = 1; mod <= 3; ++mod) {
            int total = 1;
            for (int i = 0; i < n; ++i) {
                total *= mod;
            }

            const auto dist = all_distances(n, mod);
            for (int a_state = 0; a_state < total; ++a_state) {
                const auto a_values = decode(a_state, n, mod);
                std::vector<long long> a(n);
                for (int i = 0; i < n; ++i) {
                    a[i] = a_values[i];
                }

                for (int b_state = 0; b_state < total; ++b_state) {
                    const auto b_values = decode(b_state, n, mod);
                    std::vector<long long> b(n);
                    std::vector<int> delta_values(n);
                    for (int i = 0; i < n; ++i) {
                        b[i] = b_values[i];
                        delta_values[i] = static_cast<int>(
                            mod_difference_ll(a[i], b[i], mod));
                    }
                    assert(minimum_mod_range_increment_decrement_operations(
                               a, b, static_cast<long long>(mod)) ==
                           dist[encode(delta_values, mod)]);
                }
            }
        }
    }

    for (int mod = 1; mod <= 4; ++mod) {
        const int n = 5;
        int total = 1;
        for (int i = 0; i < n; ++i) {
            total *= mod;
        }

        const auto dist = all_distances(n, mod);
        std::vector<long long> a(n, 0);
        for (int b_state = 0; b_state < total; ++b_state) {
            const auto b_values = decode(b_state, n, mod);
            std::vector<long long> b(n);
            for (int i = 0; i < n; ++i) {
                b[i] = b_values[i];
            }
            assert(minimum_mod_range_increment_decrement_operations(
                       a, b, static_cast<long long>(mod)) == dist[b_state]);
        }
    }
}
} // namespace

int main() {
    self_test();
    return 0;
}

Back to top page