A - 高橋君とお肉
ARC29のA問題
bit全探索をうまく使うと解ける問題。
def solve():
N = int(input())
tlist = [int(input()) for i in range(N)]
ans = 10**5
# pattern数は2**n
for i in range(2 ** N):
a, b = 0, 0
for j in range(N):
if (i >> j) & 1:
a += tlist[j]
else:
b += tlist[j]
ans = min(ans, max(a, b))
print(ans)
if __name__ == "__main__":
solve()
bit全探索は、下記記事がわかりやすい。
まず、すべてのパターンは、N個の中から焼く、やかないの二通りなので、2 ** N通りとなる。
そして、見慣れないbit演算if (i >> j) & 1:が出てくる
まず、i >> jは、右シフトを意味する。
11 >> 1
1011 = 11
------------
0101 = 5
続いて、 & は論理積を意味する。
10 & 12
1010 = 10
1100 = 12
------------
1000 = 08
2nの2進数のそれぞれの桁が 0 であるのか 1 であるのかを確認できれば、すべての組み合わせを確認できることになる。
ここでポイントになるのは、2nの２進数はn桁になること。
なので、フラグが立っている=それが存在するとして、順にその対象を詰めていくことで走破することができる。
あとは各組み合わせパターン事に大きさを比較していけば良い。