2025/09/26 追記： https://www.docswell.com/s/hitonanode/K2QGL9-2025-09-26-235147 にスライド版の解説があります

列 \(A\) と \(B\) が与えられたとき、以下の貪欲法を適用することを考えます。

1. \(A\) の先頭の要素から割当を決めていく。 \(A_i\) は、その時点で山の空き容量が \(A_i\) 以上のもののなかで最も小さいものに割り当てる（そのような山が存在しなければ、どの山にも割当を行わない）。

これに用いる \(A\) は以下のように構築することにします。

1. 本問題のテストケースを手元で \(K = 1{,}000\) 個程度ランダム生成する。
2. \(A\) が空の状態から始め、以下の処理を \(N = 500\) 回繰り返す。
   1. 各テストケースに上述の貪欲アルゴリズムを適用し、空き容量の最大値を求める。 \(K\) 個の値が得られる。
   2. この \(K\) 個の値から一つを選び \(A\) の要素に追加する。追加する要素の選び方は、この \(K\) 個の値を昇順ソートした列 \(C\) を作って、 \(C_i \cdot (K + 1 - i)\) が最大となるような \(C_i\) (\(1 \le i \le K)\) とする（直感的には、上述の貪欲アルゴリズムで次に追加すると最も効率的に空き容量を減らせそうな要素を選んでいる）。
   3. \(A\) を降順ソートする。

提出 https://atcoder.jp/contests/ahc053/submissions/69275661 (120B 点) はこの方針を実装したものです。この提出に埋め込まれている \(A\) は以下のコードで生成されます。

import bisect
import copy

import numpy as np

_DEFAULT_SEED: int = 20250913
N = 500
M = 50
L = 998000000000000
R = 1002000000000000

rng = np.random.default_rng(_DEFAULT_SEED)

testcases = [
    sorted([int(x) for x in rng.integers(L, R + 1, size=M, dtype=np.int64)])
    for _ in range(1000)
]


def Greedy(A: list[int], B: list[int]) -> list[int]:
    A = copy.copy(A)
    remains = copy.copy(B)
    A.sort(reverse=True)
    remains.sort()

    for a in A:
        idx = bisect.bisect_left(remains, a)
        if idx < len(remains):
            remains[idx] -= a
            val = remains.pop(idx)
            bisect.insort(remains, val)

    return remains


def DecideNextA(maximums: list[int]) -> int:
    maximums = copy.copy(maximums)
    maximums.sort()

    max_red = -1
    ret = 0

    for i in range(len(maximums)):
        m = maximums[i]
        red = m * (len(maximums) - i)
        if red > max_red:
            max_red = red
            ret = m
    return ret


def BuildA() -> list[int]:
    ret: list[int] = []

    for _ in range(N):
        ret.sort(reverse=True)

        maximums: list[int] = []
        for b in testcases:
            r = Greedy(ret, b)
            maximums.append(max(r))
        g = DecideNextA(maximums)
        ret.append(g)

    return ret


A = BuildA()

print(A)