トップ > AtCoder > ABC240F - Sum Sum Max

ABC240F - Sum Sum Max

AtCoder AtCoder-Beginner Contest 手計算 和-累積和 Python

考え方

数列$C$の等しい部分に分割して考えて，それぞれの区間での$A_{1},...,A_{M}$の最大値が$O(1)$で求められれば，全体では$O(N)$計算できる．

数列$C$の要素が全て$a$である区間を考える．$B,A$の前の区間からの持ち越し分を$b_{0}, a_{0}$とすれば，

$1$ $2$ $\cdots$ $i$ $\cdots$ $y$
$C$ $x$ $x$ $\cdots$ $x$ $\cdots$ $x$
$B$ $x + b_{0}$ $2x + b_{0}$ $\cdots$ $ix + b_{0}$ $\cdots$ $yx + b_{0}$
$A$ $x + b_{0} + a_{0}$ $3x + 2b_{0} + a_{0}$ $\cdots$ $i(i + 1)x/2 + i b_{0} + a_{0}$ $\cdots$ $y(y + 1)x/2 + y b_{0} + a_{0}$
となる．

ここで，

\begin{aligned}
A(i)
&= \frac{x}{2} \biggl[i^{2} + \biggl(1 + \frac{2b_{0}}{x}\biggr) i + \frac{2a_{0}}{x}\biggr] \\
&= \frac{x}{2} \biggl[i + \frac{1}{2}\biggl(1 + \frac{2b_{0}}{x} \biggr) \biggr]^{2} + \mathrm{const.}
\end{aligned}
だから，最大になり得るのは
\begin{aligned}
i = 0, y,
\biggl\lfloor -\frac{1}{2}\biggl(1 + \frac{2b_{0}}{x} \biggr)\biggr\rfloor,
\biggl\lceil -\frac{1}{2}\biggl(1 + \frac{2b_{0}}{x} \biggr) \biggr\rceil
\end{aligned}
のいずれか（最後の2つが必要になるのは$A(i)$が上凸になる$x < 0$の場合だけ）．

【参考】【解説 実況】ABC240 F問題【かつっぱ】 - YouTube (Submission #29533488 - AtCoder Beginner Contest 240)


回答例

T = int(input())

def A(i, x, a0, b0):
    return i * (i + 1) * x // 2 + i * b0 + a0

def calc(x, y, a0, b0):
    ret = max(A(1, x, a0, b0), A(y, x, a0, b0))
    if x < 0:
        i_floor = (x + 2 * b0) // (2 * (- x))
        i_ceil = (x + 2 * b0 + 2 * (- x) - 1) // (2 * (- x))
        if 1 <= i_floor <= y:
            ret = max(ret, A(i_floor, x, a0, b0))
        if 1 <= i_ceil <= y:
            ret = max(ret, A(i_ceil, x, a0, b0))
    return ret

for _ in range(T):
    N, M = map(int, input().split())
    ans = - 1 << 60 
    a0, b0 = 0, 0
    for _ in range(N):
        x, y = map(int, input().split())
        ans = max(ans, calc(x, y, a0, b0))
        a0 = A(y, x, a0, b0)
        b0 += y * x
    print(ans)

参考