ICPC2021応援メッセージ（アジア地区大会）「3人で問題を分け合って……」の問題 editorial

n = 22
a = [(i + 1) ** 2 for i in range(n)]

cost = [0] * (1 << n)
for s in range(1 << n):
    for i in range(n):
        if s >> i & 1:
            cost[s] += a[i]

INF = 123456789
dp = [INF] * (1 << n)
# dp[s]: sで表される集合に含まれる問題を2人ですべて解くときの最適値
# = 問題集合sの2分割の仕方すべてに渡る
#   「max(人1担当の問題を解く合計時間, それ以外の問題(人2担当の問題)を解く合計時間)」の最小値
dp[0] = 0
for s in range(1 << n):
    for i in range(n):
        if s >> i & 1:
            t = s ^ (1 << i)
            # t(の一部)を解くのにかけた時間がdの人とeの人
            d = dp[t]
            e = cost[t] - d
            dp[s] = min(
                dp[s],
                max(d + a[i], e),  # 1人目がiを解く
                max(d, e + a[i]),  # 2人目がiを解く
            )

ans = INF
for s in range(1 << n):
    t = ((1 << n) - 1) ^ s
    ans = min(ans, max(
        cost[s],  # 人3担当の問題を解く合計時間
        dp[t],
    ))
print(ans)

x, y = None, None
for s in range(1 << n):
    if ans == cost[s]:
        t = ((1 << n) - 1) ^ s
        if ans == max(cost[s], dp[t]):
            x, y = s, t
            break
assert x is not None
assert y is not None
z = None
for s in range(1 << n):
    if (s | y) == y:  # sがyの部分集合か
        t = y ^ s
        if dp[y] == max(cost[s], cost[t]):
            y, z = s, t
            break
assert z is not None
assert (x ^ y ^ z) == (1 << n) - 1
assert ans == max(cost[x], cost[y], cost[z])
print([(i + 1) ** 2 for i in range(n) if x >> i & 1])
print([(i + 1) ** 2 for i in range(n) if y >> i & 1])
print([(i + 1) ** 2 for i in range(n) if z >> i & 1])