Zenn
👨‍👧‍👦

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

2022/04/03に公開
競技プログラミング
tech

問題

ICPC では個人の練習量のみならず、チームワークもとても大事になってきます。
そこで、次の問題を解いてみてください
22 問の問題があり、解くのにそれぞれ 1^2, 2^2, …, 22^2 分かかります。
3 人で問題を分け合って、かかる合計時間が最も長い人の時間を最小化してください。

https://icpc.iisf.or.jp/2021-yokohama/ouenasia/

ありうる問題の分け方は 3^{22} = 31381059609 通りあるため、単純に全ての可能性を試すやり方より効率的な解法が必要です。

解法

一人が担当する問題の集合を固定して考えると、残りの問題集合について\clubsuit:「2人で問題を分け合って、かかる合計時間が最も長い人の時間を最小化」の答えがわかればよいです。

そして、2^{22} 通りある、{問題1, 問題2, ..., 問題22} の全ての部分集合について、\clubsuit を解くのはいわゆる bitDP でできます。次のような考察から漸化式を立てられます。

  • 問題番号とかかる時間の関係を a とする、つまり a(i) = i^2 \ (i = 1, 2, \dots, 22) とする
  • 問題集合 S \subseteq \{1, 2, \dots, 22\} についての \clubsuit の答えを f(S) とする
  • 問題集合 S を解く 1 人目担当分の時間、2 人目担当分の時間はそれぞれ↓となる
    • f(S)
    • \sum_{i \in S}a(i) - f(S)

実装例

上の解法を実装することにより、応援メッセージの問題の答えは 1265 とわかります。

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)

解の構成

実際に各チームメンバーがどの問題を解くことになるかの一例です。

  1. 4, 16, 25, 36, 49, 64, 81, 144, 169, 196, 225, 256
  2. 100, 324, 400, 441
  3. 1, 9, 121, 289, 361, 484

最適値を達成する解は、たとえば次のように、担当する問題集合を一人ずつ決めていくことにより構成できます。

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])

wandbox での実行結果↓

https://wandbox.org/permlink/ixb8wIgtTFyFrwAz

Discussion