AtCoder Beginner Contest 467 E,F問題メモ

AtCoder Beginner Contest 467

E - Adjacent Sums (hard)

問題文

$0$ 以上 $M-1$ 以下の整数からなる整数列 $A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_{N-1})$ が与えられます。
$A,B$ の長さはそれぞれ $N,N-1$ です。
$A$ に対して以下の操作を好きな回数行うことができます。
- $1$ 以上 $N$ 以下の整数 $i$ を $1$ つ選び、$A_i$ に $1$ を加える。
以下の条件を満たすようにするために必要な操作回数の最小値を求めてください。
- $i=1,2,\dots,N-1$ について、$A_i+A_{i+1}$ を $M$ で割った余りは $B_i$ に等しい。

制約

$2 \leq N \leq 2 \times 10^5$
$3 \leq M \leq 10^9$
$0 \leq A_i \leq M-1$
$0 \leq B_i \leq M-1$
入力される値はすべて整数

解法

$N-1$ 個ある隣接2要素1組に対して、「この2つには合計で $k \bmod{M}$ 回操作が必要」という値が決まっている。まず、$A,B$ からその値（$C_1,...,C_{N-1}$ とする）に変換してから考える。

$C_i = (B_i - A_i - A_{i+1}) \bmod{M}$

(例) M=15
i  1  2  3  4  5  6
C |-10-||--7-||--5-|
     |--8-||--0-|

$A_1$ に加算する値 $D_1$ を固定すると、$A_2,...,A_N$ に加算する値 $D_2,...,D_N$ も全部決まる。
$D_1$ を $0,1,2,...$ と試してみると、

i  1  2  3  4  5  6
C |-10-||--7-||--5-|
     |--8-||--0-|

D  0 10 13  9  6 14
          ↓         基本は i 奇数は1増え、偶数は1減る
   1  9 14  8  7 13
          ↓         M-1から増えるときは、0になる
   2  8  0  7  8 12
   :
   8  2  6  1 14  6
          ↓
   9  1  7  0  0  5
          ↓         0から減るときは、M-1になる
  10  0  8 14  1  4

$D_1$ を $0,1,...,M-1$ まで増やすとき、各 $D_i$ について、$M-1→0$ または $0→M-1$ を跨ぐのは高々1回である。そうなる時の $D_1$ の値も、$i$ の偶奇と、$D_1=0$ の時の各 $D_i$ の値から求められる。

どの要素も跨ぎが発生しないとき、$D_1$ を1増やすときの操作回数の増分は、

$N$ 偶数の時、相殺して $0$
$N$ 奇数の時、奇数が1つだけ多いので $1$

跨ぎが発生するときは、さらに以下の増分が加えられる。

$i$ 奇数で跨ぎが発生するとき、1つあたり $-M$
$i$ 偶数で跨ぎが発生するとき、1つあたり $+M$

$D_1=0$ の時からの差分を考え、跨ぎが発生する $D_1$ の値だけをチェックすることで、全ての状態を網羅できる。

Python3

from collections import defaultdict


def solve(n, m, aaa, bbb):
    events = defaultdict(int)
    events[m] -= 1
    tmp = 0
    prev = 0
    for i in range(n - 1):
        rem = (bbb[i] - aaa[i] - aaa[i + 1]) % m
        k = (rem - prev) % m  # aaa[0] への加算が0の時、aaa[i+1] への加算値
        # print(f'  {i=} {rem=} {k=}')
        tmp += k
        if i % 2 == 0:
            # aaa[0] への加算値を1増やすと減少、k → k+1 で 0→m-1 に
            events[k + 1] += 1
        else:
            # aaa[0] への加算値を1増やすと増加、m-k → m-k+1 で m-1→0 に
            events[m - k] -= 1
        prev = k

    ans = tmp
    events = sorted(events.items())
    a0 = 0
    inc = n % 2  # aaa[0] を 1 増やして、繰り上がり下がりが発生しないときに全体が増える数
    for k, c in events:
        d = k - a0
        tmp += d * inc
        tmp += m * c
        ans = min(ans, tmp)
        a0 = k
    return ans


n, m = list(map(int, input().split()))
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ans = solve(n, m, aaa, bbb)
print(ans)

F - Email Scheduling Optimization

問題文

長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N),\;B=(B_1,B_2,\dots,B_N)$ が与えられます。
$Q$ 個のクエリが与えられます。各クエリは以下の $2$ 種類のいずれかです。
- 1 i x : $A_i$ を $x$ に変更する。
- 2 i x : $B_i$ を $x$ に変更する。
各クエリを処理するたびに、以下の問題の答えを求めてください。
- 高橋君は $N$ 個の会社にメールを送り、それぞれの会社から返信をもらう必要があります。
- $j$ 個目の会社に送るメールを書くには $A_j$ 分の時間を要し、送ってから $B_j$ 分後に返信が届きます。
- 高橋君は時刻 $0$ からメールを書き始めます。
- 高橋君は $N$ 通のメールを好きな順番で書くことができますが、$2$ 通以上のメールを同時に書くことはできません。
- 高橋君がすべての返信を受け取り終える時刻としてあり得る最小値を求めてください。
- ただし、メールを送るのにかかる時間は無視できるものとします。

制約

$1 \leq N \leq 10^5$
$1 \leq Q \leq 10^5$
$1 \leq A_j,B_j \leq 10^9$
各クエリにおいて、$1 \leq i \leq N$
各クエリにおいて、$1 \leq x \leq 10^9$
入力される値はすべて整数

解法

更新が無いとき

まず $A,B$ の更新を考えないときの問題の解き方を考える。

直感的には、返信に時間がかかる（$B_i$ が大きい）順に書いた方が、待ってる間に他のメールを書くことで時間の節約になりそう。

そしてそれは正しい。
$B$ が降順になるように（$A$ も合わせて）並べ直し、その順に送るとして、$i$ と $i+1$ を入れ替えたときに得をすることがないことから証明できる。

公式Editorial

よって問題の答えは、以下のMAXとなる。（$B$ は降順にソート済みとする）

$\displaystyle \max_i \sum_{j=1}^{i}A_j+B_i$

A   3  1  4  1  5
B   9  7  4  4  1

A   3→1→4→1→5
    v  v  v  v  v
B   9  7  4  4  1
  ----------------
和 12 11 12 13 15  →  maxは15

更新を考慮するとき

$B$ の大きさが関わってくるので、これを index に持ったセグメント木に載せることを考える。
（実際は $B \le 10^9$ と大きいので、座標圧縮する）

各ノードは、「$B_i$ の値が $[l,r)$ であるような $i$」について集約した情報を表し、以下の2つの情報を持てば良い。

区間内の $A_i$ の総和
区間内の各 $B_i$ に対して「（区間内の、$B_j \ge B_i$ である $j$ に対する $A_j$ の総和）$+B_i$」のmax

$B_i$ が同じ要素が複数ある場合、全ての $A_i$ の総和を載せておく。
また、実際には要素がない（過去または将来に $B_i=x$ となる要素が存在しうるが、今現在は $B_i=x$ となる要素はない）場合、$x$ における後者の値は $x$ ではなく $-\infty$ としておく必要がある点に注意。