この解説では、絶対値の和は以下の式のことを言います。

\[\sum_{j=1}^{L - 1}\sum_{k = j + 1} ^ {L} |B_{j} - B_{k}|\]

\(B\) が存在するとき、\(\max(B)\) の最小値を取ることができる \(B\) のうち \(1\) つは、以下の \(2\) つの条件を満たします。

• \(B\) が昇順ソートされている
• \(B_{1} = 0\)

\(1\) つ目の条件は、絶対値の和が \(B\) の順番によらないことから成り立ちます。 \(2\) つ目の条件は \(B\) の要素が全て正なら、全ての要素から \(1\) を引くことで、 絶対値の和を変えずに、\(\max(B)\) を小さくできることから成り立ちます。

\(B\) が昇順ソートされているとき、絶対値の和は以下のように表せます。

\[\sum_{j = 1}^{L - 1}\sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = \sum_{j = 1}^{L - 1}\sum_{k = j + 1} ^ {L} (B_{k} - B_{j}) =\sum_{k = 1} ^ {L - 1} k(L - k)(B_{k + 1} - B_{k})\]

この式変形が正しいことは、\(1\leq b<a\leq L\) を満たす整数 \(a,b\) に対して、 \(B_{a}-B_{b}=(B_{a}-B_{a-1}) + (B_{a-1}+B_{a-2}) + \cdots +(B_{b+1}-B_{b})\) が成り立つことと、\(b\leq k\) かつ \(k+1\leq a\) が成り立つ整数の組 \((a,b)\) が \(k(L-k)\) 通りであることから示せます。

\(C_{k} = B_{k + 1} - B_{k}\) とすると、\(B\) が昇順ソートされているかつ \(B_{1} = 0\) のとき、以下が成り立ちます。

• \(0 \leq C_{k}\)
• 絶対値の和は \(\displaystyle \sum_{k = 1} ^ {L - 1} k(L - k)C_{k}\) と等しい。
• \(\displaystyle\max(B) = B_{L} = \sum_{k = 1} ^ {L - 1} C_{k}\)

よって、以下の問題が解ければ良いです。

長さ \(L - 1\) の非負整数列 \(C\) で、\(\displaystyle \sum_{k = 1} ^ {L - 1} k(L - k)C_{k} = A_{i}\) を満たすようなものが存在するか判定し、存在するならそのような \(C\) に対する、\(C\) の総和の最小値を求めてください。

これはナップザック問題と同じ要領の動的計画法で、全ての \(i\) に対して同時に求めることができます。

\(\max(A)<k(L-k)\) を満たすような \(k\) に対して \(C_{k} = 0\) が常に成り立つことから、空間計算量 \(O(\max(A))\) 時間計算量 \(O(N + \max(A)\sqrt{\max(A)})\) で求まります。

c++ による実装例

python による実装例

# input
N, L = map(int, input().split())
A = list(map(int, input().split()))

# init
M = 2 * 10 ** 5
INF = 10 ** 9
dp = [INF] * (M + 1)
dp[0] = 0
k = 1

# dp
while k * (L - k) <= M and k * 2 <= L:
    # upd
    w = k * (L - k)
    for i in range(w, M + 1):
        dp[i] = min(dp[i], dp[i - w] + 1)
    # inc
    k += 1

# output
for a in A:
    print(-1 if dp[a] == INF else dp[a])