ABC374 C問題の解説（Python）

はじめに

この記事では、ABC374のC問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

ABC374　C – Separated Lunch

問題

問題

ある会社にはN個の部署が存在し、\(i\) 番目の部署に所属する人数は \(K_i\) 人です。

それぞれの部署をグループ A, B のいずれか一方に割り当てます。グループ A に割り当てられた部署に所属する人数の合計とグループ B に割り当てられた部署に所属する人数の合計のうち大きい方の値としてあり得る最小の値を求める問題です。

制約

• \(2 \leqq N \leqq 20 \)
• \(1 \leqq K_i \leqq 10^{18} \)

思考の筋道

グループAの合計人数とグループBの合計人数のうち大きい方の人数をなるべく小さくしたいという問題です。片方のグループに人数が偏らず、同じくらいの人数になってほしいということですね。

さて、この問題で注目すべきは、部署は最大でも20までしかないということです。

それぞれの部署をグループ A, B のいずれか一方に割り当てるわけですが、20の部署であれば割り当てを全パターン試すことができます。

さて、N重のfor文は作りたくありません。このような時にはbit全探索という手法を用います。

bitが1ならその部署はグループAに振り分け、グループAの合計人数に加えます。反対に、bitが0ならその部署はグループBに振り分け、グループBの合計人数に加えます。

すべての部署を振り分けたら、グループAの合計人数とグループBの合計人数を比べ、大きい方の人数がこれまでの最小値より小さくなるかを調べていけばOKですね！

bit全探索はC問題あたりから時々使うことがありますので、使えるようにしておきましょう。

コード

N = int(input())
K = list(map(int, input().split()))

min = 2 ** 31 - 1

for i in range(2 ** N):
    sum_A = 0
    sum_B = 0
    for j in range(N):
        if (i >> j) & 1:
            sum_A += K[j]
        else:
            sum_B += K[j]
    if max(sum_A, sum_B) < min:
        min = max(sum_A, sum_B)

print(min)

以上、ABC374のC問題の解説でした！

では、またね。

リンク