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

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-05-18 15:10:34+09:00
• Include: #include "other/minimum-mod-range-increment-decrement-operations.hpp"

概要

• 数列を $\text{mod }m$ 上で見たとき、区間に $+1$ または $-1$ を 1 回加える操作の最小回数を求める。
• 区間に整数 $x$ を加える操作の最小 $\sum \lvert x\rvert$ と同値である。
• $c_i = (b_i - a_i) \bmod m$ の階差を $[0, m)$ で取り、その総和が $Cm$ になることを使って大きい値から $C$ 個を負側に回す。

使い方

• T minimum_mod_range_increment_decrement_operations(std::vector<T> a, std::vector<T> b, T m)
  • $a$ を $b$ に一致させるための最小操作回数を返す。
  • 前提：$\lvert a\rvert=\lvert b\rvert,\,m>0,\,0\le a_i,b_i<m$。
  • 前提：T は 64 bit 整数型、$m\le 10^9$ を想定する。
  • 備考：区間に整数 $x$ を加える操作を許す場合の最小 $\sum \lvert x\rvert$ と同じ値を返す。
  • 備考：実装は階差の総和そのものは持たず、$\left\lfloor \sum d_i / m \right\rfloor$ を繰り上がりで求める。
  • 備考：返り値が T に収まらない場合はオーバーフローする。

計算量

• 時間：$O(N \log N)$
• 空間：$O(N)$

Verified with

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

Code

#ifndef OTHER_MINIMUM_MOD_RANGE_INCREMENT_DECREMENT_OPERATIONS_HPP
#define 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>
#include <cassert>
#include <cstddef>
#include <type_traits>
#include <vector>

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

#endif

#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>
#include <cassert>
#include <cstddef>
#include <type_traits>
#include <vector>

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

Back to top page