ABC374 C - Separated Lunch

はじめに

10/5開催のABC372のC問題の復習です。

問題文

キーエンス本社に勤務する人数が増えてきたので、本社に存在する部署を$2$つのグループに分け、昼休みの時間帯を分けることにしました。

キーエンス本社には$N$個の部署が存在し$i$番目$(1≤i≤N)$の部署に所属する人数は$K_i$人です。

それぞれの部署をグループ$A, B$のいずれか一方に割り当て、グループごとに同時に昼休みをとり、 かつグループ$A, B$の昼休みの時間が重ならないようにしたとき、同時に昼休みをとる最大人数としてあり得る最小の値を求めてください。
すなわち、グループ$A$に割り当てられた部署に所属する人数の合計とグループ$B$に割り当てられた部署に所属する人数の合計 のうち大きい方の値としてあり得る最小の値を求めてください。

考え方

すべての部署を$A,B$の$2$グループに分けて、最大値が小さい分け方を探す。
部署$N$が$20$以下なので全探索でも十分対応できそうです。

『選ぶ・選ばない』の全探索ならbit全探索を使ってときます。

解答例

ABC374_C

def optimize_groups(N, K):
    min_max_group = sum(K)

    # N部署のグループA=1,グループB=0としてbit全探索
    for i in range(1 << N):
        group_a = 0
        group_b = 0
        
        # 各部署をグループAかBに割り当てる
        for j in range(N):
            if i & (1 << j):
                group_a += K[j]
            else:
                group_b += K[j]
        
        # 大きい方のグループの人数を記録
        max_group = max(group_a, group_b)
        
        # 最小値を更新
        min_max_group = min(min_max_group, max_group)
    
    return min_max_group

# 入力を受け取る
N = int(input())
K = list(map(int, input().split()))

# 結果を出力
result = optimize_groups(N, K)
print(result)

おわりに

bit全探索の勉強になりました。
精進します！