AtCoder Talent Quest 〜 今から28卒には脱出してもらいます〜予選 #2（AtCoder Beginner Contest 480）E,F問題メモ

def solve(n):
    def prod_overflow(a, b, limit):
        if b == 0:
            return 0
        if a > limit // b:
            return -1
        return a * b

    ans = 0
    for a in range(1, 10 ** 6 + 1):
        for m in range(3, 20):
            t = a
            for k in range(1, m):
                t = prod_overflow(t, a + k, n)
                if t == -1:
                    break
            if t == -1:
                break
            l = 1
            r = 10 ** 9 + 5
            while l + 1 < r:
                mid = (l + r) // 2
                t = a
                for k in range(1, m):
                    t = prod_overflow(t, a + k * mid, n)
                    if t == -1:
                        break
                if t == -1:
                    r = mid
                else:
                    l = mid
            ans += l
            # print(f'{d=} {m=} {l=}')
    return ans

n = int(input())
ans = solve(n)
print(ans)

以下のDPは、逆に切断回数を直接求めている。

def solve(n, m, aaa):
    def iter_bit(bitset):
        while bitset:
            lsb = bitset & -bitset
            yield lsb
            bitset ^= lsb

    s = sum(aaa)
    t = s // m
    satisfied = [0] * (1 << n)
    remaining = [0] * (1 << n)
    for bitset in range(1, 1 << n):
        lsb = bitset & -bitset
        i = lsb.bit_length() - 1
        r = remaining[bitset ^ lsb] + aaa[i]
        d, r = divmod(r, t)
        satisfied[bitset] = satisfied[bitset ^ lsb] + d
        remaining[bitset] = r
    # print(f'{satisfied=}')
    # print(f'{remaining=}')
    INF = 1 << 60
    dp = [INF] * (1 << n)
    dp[0] = 0
    for bitset in range(1, 1 << n):
        best = INF
        for b in iter_bit(bitset):
            i = b.bit_length() - 1
            d, r = divmod(aaa[i], t)
            if r == 0:
                best = min(best, dp[bitset ^ b] + d - 1)
            else:
                r += remaining[bitset ^ b]
                if r <= t:
                    best = min(best, dp[bitset ^ b] + d)
                else:
                    best = min(best, dp[bitset ^ b] + d + 1)
        dp[bitset] = best

    return dp[-1]


n, m = list(map(int, input().split()))
aaa = list(map(int, input().split()))
ans = solve(n, m, aaa)
print(ans)