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

東京海上日動プログラミングコンテスト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$ によって求められる。

操作回数の式は、「$N$ 個の箱があり、箱 $i$ にはボールが $A_i$ 個ある。1回の操作で1個のボールを次の箱に移せる」と捉えると理解しやすい。 「ある1個のボールが操作前 $i$、操作後 $j$ にあったとすると、そのボールへの操作回数は $j-i$」ということから、 総操作回数は「全てのボールに対する操作後（$j$）についての合計値 - 操作前（$i$）についての合計値」となる。

$B$ が一意に決まる略証

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

ある区間 $l,r$ について、$l \le i \lt r$ を満たす全ての $i$ に少なくとも1回は操作したとする。
この時、最小回数を達成する上では、$B_l$ と $B_r$ の差は高々 $1$ である。

∵そうでないとすると、区間内に段差が $2$ 個以上あるか、高さ $2$ 以上の段差があることになる。 前者の場合、最初の段差から最後の段差までの操作を1回ずつキャンセルしても、広義単調増加は達成できていたことになる。 後者の場合も、段差の箇所の操作1回は無駄である。

そのような区間を $[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_i$ をそれぞれ、$N$ 個の長さ1の区間とする。
• 隣接する2つの区間 $[l,m], [m+1,r]$ に対し、$A_m \gt A_{m+1}$ なら区間をマージし、平坦に均す。
• なくなるまでマージを繰り返したものが $B$ である。

この時、好きな箇所から区間をマージしてよい。 つまり、「$i,i+1$ 間をマージしたけど、後になって、やっぱりそこではマージする必要はなかった」ということは発生しない。

$A_i \gt A_{i+1}$ なる状態を解消するには、$i$ に操作するしかない。 他の箇所への操作が、間接的に $A_i \gt A_{i+1}$ の状態を改善してくれることはない。 つまり、既存のマージされた区間内への操作は全て必要なものである。
その中で、均すという操作は、極力左端を大きく、右端を小さくし、$A_m \gt A_{m+1}$ となる箇所を最小化するものである。

たとえば先頭からマージすることにすると、これは $(値 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)

G - Golf 2

• 整数 $A,B,X,Y$ が与えられます。
• 二次元平面上にコマが置かれています。はじめコマは座標 $(0,0)$ にあります。
• あなたは以下の操作を $0$ 回以上何回でも行うことができます：
  • 今コマがある座標を $(x,y)$ として、以下の条件のいずれかを満たす座標 $(x',y')$ にコマを移動させる。
    • $|x-x'|=A$ かつ $|y-y'|=B$
    • $|x-x'|=B$ かつ $|y-y'|=A$
• コマを座標 $(X,Y)$ に移動させることが可能か判定し、可能であれば必要な操作回数の最小値を求めてください。

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

• $1\le T\le 2\times 10^5$
• $1\le A \lt B \le 10^6$
• $0\le X,Y\le 10^6$
• 入力される値は全て整数

コマは $\mathrm{GCD}(A,B)$ の倍数座標しか動けないので、$X,Y$ も $\mathrm{GCD}(A,B)$ の倍数である必要がある。 そうでない場合不可能。

$A,B,X,Y$ 全てを $\mathrm{GCD}(A,B)$ で割って考えても答えは変わらないので、 以下、$\mathrm{GCD}(A,B)=1$ のケースを考える。

$A,B$ がともに奇数の時、座標を市松模様のマス目と考えて スタート地点と同じ色にしか行けないので、$(X,Y)$ が違う色（$X$ と $Y$ の偶奇が不一致）の場合は不可能。

以下、これ以外の場合を考える。まだ必ず達成可能とはわからない。（結果的には達成可能だが）

上下左右にそれぞれ $A,B$ 動いた回数を、非負整数を取る $a～h$ の8変数で表して

• $A \times a + (-A) \times b + B \times c + (-B) \times d = X$
• $A \times e + (-A) \times f + B \times g + (-B) \times h = Y$

ここで、$u_1=a-b,u_2=c-d,u_3=e-f,u_4=g-h$ とまとめる。

• $A \times u_1 + B \times u_2 = X$
• $A \times u_3 + B \times u_4 = Y$

また、$x$ 軸方向に $A$ 動かす操作を選んだとき、$y$ 軸方向には $B$ 動くことになる。つまり、

• $a+b=g+h$
• $c+d=e+f$

が成り立っている必要がある。 この条件は、正と負をセットで追加することで偶数回なら操作回数を好きに増やせるので、

• $u_1 \equiv u_4 \mod{2}$
• $u_2 \equiv u_3 \mod{2}$

が成り立っていればよいということになる。

また、操作回数最小化の上では $a,b,g,h$ の全てが正であることは無い。全てを $1$ ずつ減らしても達成可否に影響しないので。

よって、全体の操作回数は $\max(|u_1|,|u_4|)+\max(|u_2|,|u_3|)$ と表せる。

まとめると、

• 以下を全て満たす整数 $u_1～u_4$ に対して
  • $A \times u_1 + B \times u_2 = X$
  • $A \times u_3 + B \times u_4 = Y$
  • $u_1 \equiv u_4 \mod{2}$
  • $u_2 \equiv u_3 \mod{2}$
• 以下の値の最小値が答え
  • $S=\max(|u_1|,|u_4|)+\max(|u_2|,|u_3|)$

これを解いていきたい。

まず、$A=B=1$ の場合を考える。 前述の不可能ケース（市松模様）に該当しない場合、答えは $\max(X,Y)$ となる。

以下、$A \neq B$ とする。

$u_1～u_4$ について、ひとまず実数でもよいとした（mod2の制約も外した）解を考えることにする。

$A \times u_1 + B \times u_2 = X$、$A \times u_3 + B \times u_4 = Y$ の2直線をプロットしたグラフをイメージする。 $A,B,X,Y$ の制約から、直線は第二～第一～第四象限を通過する。

u2,u3↑
  X/B│\
     │ \
  Y/A│--\,,
     │   \ --,,
     ┼──\────→u1,u4
          X/A   Y/B

このグラフ上で $S$ の最小値を考えるとすると、

• 2本の直線上から、それぞれ1点選ぶ
• 選んだ点が第二象限、第四象限の場合は、それぞれ $y,x$ 軸で反転させて第一象限に移す
• 左下が $(0,0)$ で、右と上は2点をぴったり含むようにした矩形を考える。
• 矩形の右上の座標の $x+y$ が、$S$ である。

ここで直線の分布から、第二象限・第四象限の点は考慮しなくてよい。 反転させたとき、$x$ 座標が同じで $y$ 座標がより小さい点（またはその逆）が、同じ直線上に必ずあるから。

少し観察すると、$S$ を最小化する $(u_1,u_2),(u_4,u_3)$ は以下になるとわかる。

• 2直線の交点が第一象限にある場合、ともに交点
• 第二象限にある場合、$(0,X/B),(0,Y/A)$
• 第四象限にある場合、$(X/A,0),(Y/B,0)$

乱暴なイメージで言うと「なるべく近い2点を取った方がお得」ということになり、これは整数解の場合でも変わらない。

よって、上記の実数解の近傍にある整数解をいくつか試し、 パリティ条件が一致する中で、$S$ が最小のものを見つければ良い。
（この時、最適解となる整数解は第二・第四象限になり得る点に注意）

整数解の1つは拡張ユークリッドの互除法などで見つけられる。
$A \times u_{10} + B \times u_{20} = X$ とすると、 整数 $k$ に対し $u_1=u_{10} + kB,u_2=u_{20}-kA$ としたものが $(u_1,u_2)$ の整数解を全て網羅する。

他の条件がパリティのみなので、探索範囲は両点、実数解の再近傍から $\pm 2$ 点、計 $25$ 点程度を試すと十分である。

• ユーザー解説
• 一般には、どんな関数でも整数解の最適解が実数解の近傍にあるとは限らない。
• 解説では、目的関数が同じ値を取る $(x,y)$ の範囲を「等高線」で結び、本問題ではそれが単純な傾きしか取らないため、格子点を避けて近傍から広げるのに限界があることを示している

Python3

from atcoder._math import _inv_gcd


def solve(a, b, x, y):
    g, kx = _inv_gcd(a, b)

    if x % g != 0 or y % g != 0:
        return -1

    a //= g
    b //= g
    x //= g
    y //= g

    # a,b 奇数の場合は、x,y の偶奇が一致している必要あり
    if a % 2 == 1 and b % 2 == 1:
        if x % 2 != y % 2:
            return -1

    if a == b:
        return max(x, y)

    # 最小回数かはともかく、A*u10 + B*u20 = X, A*u30 + B*u40 = Y となる u10,u20,u30,u40 を仮定
    ky = -(kx * a // b)
    u10, u20 = kx * x, ky * x
    u30, u40 = kx * y, ky * y

    s0 = (a * x - b * y) // (a ** 2 - b ** 2)
    t0 = (a * y - b * x) // (a ** 2 - b ** 2)
    if s0 < 0:
        s0 = 0
        t0 = y // a
    elif t0 < 0:
        s0 = x // a
        t0 = 0

    k_center = (s0 - u10) // b
    l_center = (t0 - u30) // b

    ans = 1 << 60
    AROUND = 4
    for k in range(k_center - AROUND, k_center + AROUND + 1):
        u1 = u10 + k * b
        u2 = u20 - k * a
        for l in range(l_center - AROUND, l_center + AROUND + 1):
            u3 = u30 + l * b
            u4 = u40 - l * a

            if u1 % 2 == u4 % 2 and u2 % 2 == u3 % 2:
                ans = min(ans, max(abs(u1), abs(u4)) + max(abs(u2), abs(u3)))

    return ans


t = int(input())
for _ in range(t):
    a, b, x, y = map(int, input().split())
    ans = solve(a, b, x, y)
    print(ans)