I was a competition professional and started studying algorithms. I will explain the bit full search, which is the beginning of the algorithm, with the meaning of the output. I am still a young student, so please point out any mistakes. I will write in the main story of the competition professional.
This is one of the full search methods. This technique can be used when there are multiple variables and each variable takes two values. A bit is a computer that takes two values, 0 and 1. It is likened to. I think it's hard to understand from the explanation of the letters, so I'll put an example on it.
0,1 Only the two numbers of can be included in the list. The length of the list is 3. List all possible lists.
bit.py
for i in range(2**3): #1
list=[0]*3 #2
for k in range(3): #3
if ((i>>k)&1): #4
list[k]=1 #5
print(list)
1 Each element in the list is 1 or 0, so the number of elements is 2 ** (the number of elements) 2 Create a temporary list. It will be rewritten later according to the result of bit operation. By the way, [0] * 3 = [0,0,0]. 3 The length of the list is 3, so you can shift it up to 2 times. 4 It is the core part of bit full search. i >> k means shift i to the left k times. Since & indicates and, this line means "i >> k means if i is shifted left k times and 1 is True".
https://atcoder.jp/contests/abc045/tasks/arc061_a
Don't bring # 2 over the for loop
Recommended Posts