東京海上日動プログラミングコンテスト2026（AtCoder Beginner Contest 459）F問題メモ

東京海上日動プログラミングコンテスト2026（AtCoder Beginner Contest 459）

F - -1, +1

• 長さ $N$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
• あなたは以下の操作を $A$ に対して $0$ 回以上好きな回数行うことができます：
  • $1\le i \le N - 1$ を満たす整数 $i$ を選び、$A_i$ を $1$ 減らし、$A_{i+1}$ を $1$ 増やす。
• $A$ を狭義単調増加列にするために必要な操作回数の最小値を求めてください。
• ただし、答えは $2^{63}$ 未満になることが証明できます。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T\le 3\times 10^5$
• $1\le N\le 2\times 10^5$
• $0\le A_i\le 10^9$
• 全てのテストケースにおける $N$ の総和は $6\times 10^5$ 以下
• 入力される値は全て整数

狭義単調増加は扱いづらいので、$A_i←A_i-i$ とすることで「広義単調増加にすればよい」という問題に置き換える。

最小回数の操作によって作れる広義単調増加な数列は一意に決まり、これを $B$ とする。 操作回数は、$\displaystyle \sum_{i=1}^{N}i \times B_i - \sum_{i=1}^{N}i \times A_i$ によって求められる。

一意に決まる略証

よって、$B$ を特定できればよい。

ある $A_i$ が小さいので $A_{i-1}$ から持ってこないといけない。 でもそうすると $A_{i-1}$ も小さくなるので $A_{i-2}$ からも持ってこないといけない、、、 ということが連鎖的に発生する。

そのような連鎖が発生した区間を $[l,r]$ とすると、操作後の区間の値は以下のようになっているはずである。

• 区間幅 $w=r-l+1$ とする。
• 区間の和 $\displaystyle \sum_{i=l}^{r}A_i$ を区間幅 $w$ で割った商を $h$、余りを $m$ とする。（$0 \le m \lt w$）
• 操作後の区間の値は、左 $w-m$ 個が $h$、右 $m$ 個が $h+1$ となっている。

この操作を、区間を「均した」ということにする。

最初、$A$ の全ては長さ1の $N$ 個の区間であるとする。

隣接する2つの均した区間で「左区間の末尾 $\gt$ 右区間の先頭」となっていた場合、 その2つの区間をまとめて全体を均してよい。

この時、好きな箇所から貪欲に区間をマージしてよい。 つまり、「$i,i+1$ 間をマージしたけど、後になって、やっぱりそこではマージする必要はなかった」ということは発生しない。
「均す」という行為は、区間の中で先頭をできるだけ大きく、末尾をできるだけ小さくする行為なので、 その上で隣接区間と「左区間の末尾 $\gt$ 右区間の先頭」となるのであれば、その隣接区間の間でもやはり操作が必要である。

たとえば先頭からマージすることにすると、これは $(値 h, 長さ w)$ を要素とした stack などによって実装できる。

Python3

def solve(n, aaa):
    aaa = [a - i for i, a in enumerate(aaa)]

    stack = [(-1 << 62, 0)]  # 高さ, 連続個数

    for a in aaa:
        height = a
        width = 1
        remain = 0
        total = a
        while stack[-1][0] >= height:
            h, w = stack.pop()
            total += h * w
            width += w
            height, remain = divmod(total, width)
        stack.append((height, width - remain))
        if remain > 0:
            stack.append((height + 1, remain))

    bfr_score = sum(i * a for i, a in enumerate(aaa))
    aft_score = 0
    i = 0
    for h, w in stack[1:]:
        for j in range(i, i + w):
            aft_score += j * h
        i += w

    ans = aft_score - bfr_score
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    print(ans)