ABC 467 E - Adjacent Sums (hard)

[river0525]

問題の感想や気づきを投稿・共有するスペースです

[sgfc]

公式解説に実装例が無かったため、誰かの役に立つかもしれないので置いておきます。

Python

# 添字はすべて 0-indexed (問題文の A_1 がコードの a[0])
from collections import defaultdict

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    # c[i] : a[0] への加算量を 0 としたときの、a[i] に必要な加算量
    # (a[i]+c[i]) + (a[i+1]+c[i+1]) ≡ b[i] (mod m) より左から順に決まる
    c = [0] * n
    for i in range(n - 1):
        c[i + 1] = (b[i] - a[i] - a[i + 1] - c[i]) % m

    sum_c = sum(c)  # t = 0 のときの必要加算量の総和

    # a[0] への加算量を t (0 <= t <= m-1) としたとき、a[i] の必要加算量は
    #   偶数番目 : c[i] + t。ただし m に達した瞬間に -m できる (t = m - c[i] で発生)
    #   奇数番目 : c[i] - t。ただし 0 未満になった瞬間に +m が必要 (t = c[i] + 1 で発生)
    # events[t] : 加算量が t に達した瞬間に総和へ加わる変化量
    events = defaultdict(int)
    for i in range(1, n):
        if i % 2 == 0:
            events[m - c[i]] -= m
        else:
            events[c[i] + 1] += m

    # t を 1 増やすごとの総和の増分
    # = (偶数番目の項数) - (奇数番目の項数) = n % 2  (a[0] 自身の +1 も含む)
    slope = n % 2

    # イベントとイベントの間では総和は一定 (n が偶数) または単調増加 (n が奇数)。
    # したがって最小値は t = 0 か、いずれかのイベントの直後でのみ達成されるので、
    # その点だけ調べればよい。
    ans = sum_c  # t = 0 の場合
    cur = sum_c  # 現在の t での総和
    prev_t = 0   # 直前に調べた t
    for t, delta in sorted(events.items()):  # dict は自動で並ばないので sorted が必要
        if t >= m:  # t = m のイベントは範囲外なので打ち切る
            break
        cur += slope * (t - prev_t) + delta
        prev_t = t
        ans = min(ans, cur)

    print(ans)

main()

C++

// 添字はすべて 0-indexed (問題文の A_1 がコードの a[0])
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n; ll m;
    cin >> n >> m;
    vector<ll> a(n), b(n-1);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;

    // x を [0, m) に正規化する 
    auto mod = [&](ll x) { return (x % m + m) % m; };

    // c[i] : a[0] への加算量を 0 としたときの、a[i] に必要な加算量
    // (a[i]+c[i]) + (a[i+1]+c[i+1]) ≡ b[i] (mod m) より左から順に決まる
    vector<ll> c(n, 0);
    for (int i = 0; i + 1 < n; ++i) {
        c[i + 1] = mod(b[i] - a[i] - a[i + 1] - c[i]);
    }

    ll sum = 0; // t = 0 のときの必要加算量の総和
    for (int i = 0; i < n; ++i) sum += c[i];

    // a[0] への加算量を t (0 <= t <= m-1) としたとき、a[i] の必要加算量は
    //   偶数番目 : c[i] + t。ただし m に達した瞬間に -m できる (t = m - c[i] で発生)
    //   奇数番目 : c[i] - t。ただし 0 未満になった瞬間に +m が必要 (t = c[i] + 1 で発生)
    // events[t] : 加算量が t に達した瞬間に総和へ加わる変化量
    // (map なので t の昇順に並び、同じ t のイベントは自動的に合算される)
    map<ll, ll> events;
    for (int i = 1; i < n; ++i) {
        if (i % 2 == 0) events[m - c[i]] -= m;
        else            events[c[i] + 1] += m;
    }

    // tを1増やすごとの総和の増分 = (偶数番目の項数)-(奇数番目の項数) = n%2  (a[0]も含む)
    ll slope = n % 2;

    // イベントとイベントの間では総和は一定 (n が偶数) または単調増加 (n が奇数)。
    // したがって最小値は t = 0 か、いずれかのイベントの直後でのみ達成されるので、その点だけ調べればよい。
    ll ans = sum;    // t = 0 の場合を答えの初期値とする
    ll cur = sum;    // 現在の t での総和
    ll prev_t = 0;   // 直前に調べた t
    for (auto [t, delta] : events) {
        cur += slope * (t - prev_t) + delta;
        prev_t = t;
        ans = min(ans, cur);
    }
    cout << ans << "\n";
}

[sec6890]

a[0]に足す数を決めるとb[0]の制約からa[1]に足す数が決まります。そうすると連鎖的にa[2],a[3]...に足す数も決まります。
ということを踏まえて、a[0]に足す数を0にしてみます。そのときの各iに足すべき数をx[i]とすると、
入力例１

3 10
4 6 7
5 5

ではx=[0,5,7]となります。このxの総和を小さくしたいです。modを無視して単純に考えると、
x[0]を1増やすと、x[1]に足す数は1減らして良くなります。しかしx[1]が減るのでx[2]は逆に1増やす必要が出てきます。
x[0]を1増やすと奇数番目は1減り、偶数番目は1増やすことになります。
nが偶数ならx[0]をいくらふやしてもxの総和は変わらなそうです。奇数なら、なるべくx[0]を増やしたくないです。
しかし、modを考えると今x[2]は7なので、もう3増えるとx[2]==M、modを取ればx[2]==0となり、
xの総和が減りそうです。これは嬉しいです。逆に、x[1]は5なので5までだったら減らしても良いですが、
6減らしてしまうと値がマイナスに突入、modを取るとx[1]==M-1となってしまいxの総和が増えて嬉しくないです。
この嬉しい／嬉しくないイベントが発生する位置を記録すると、

嬉しい→0,3
嬉しくない→6

となります。xの偶数番目の項はいつ嬉しいか、奇数番目の項はいつ嬉しくないかを計算するのに使います。
嬉しいとき1増え、嬉しくないとき1減る嬉しい度という値を定義します。
0のとき1増え、3のとき1増え、6のとき1減る、この累積和を取るといつが一番うれしいか分かります。
一番うれしい度が高くなった瞬間、この場合は3の値がx[0]として設定すべき値です。
あとはa[0]をこのとおりに増やしたとき、各項はいくつ足すことになるのか順に計算してき、
その和を取ると答えです。