Solve with Python [100 selected past questions that beginners and intermediates should solve] (010 --014 Full search: Bit full search)
1. Purpose
Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.
This article is "010 --014 Full Search: Bit Full Search".
2. Summary
Until now, `itertools.product``` was used to generate `(0, 1) ``` when performing a full bit search, but I tried to solve it with bit shift for later. ..
3. Main story
010 --014 Full search: Bit full search
010. ALDS_5_A --Brute force
Answer
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
check_list = [0] * (2000 * 20 + 1)
for i in range(2**n):
total = 0
for j in range(n):
if (i >> j) & 1:
total += A[j]
check_list[total] = 1
for m in M:
if check_list[m]:
print('yes')
else:
print('no')
Determines whether all elements in the list A are "used" or "not used", and whether the total is included in the list M```. At first, I used the following code, but it was a triple for loop and I couldn't make it in time. Flag the check_list``` with the calculated `` total as a subscript because the speed will be slower when comparing the calculated `` `total with the `m``` each time. You need to check the subscript `m``` again after that.
#I can't make it in time
n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
for m in M:
ans = 'no'
for i in range(2**n):
total = 0
for j in range(n):
if (i >> j) & 1:
total += A[j]
if total == m:
ans = 'yes'
break
print(ans)
Answer
N, M = map(int, input().split()) #N is the number of switches, M is the number of light bulbs
lights = [[0] * N for _ in range(M)]
for i in range(M):
temp = list(map(int, input().split())) #The 0th indicates the number of switches, and the 1st and subsequent switches indicate the switches.
k = temp[0]
switches = temp[1:]
for j in range(k):
lights[i][switches[j]-1] = 1
P = list(map(int, input().split())) #Lights when the number divided by 2 is equal to the element
answer_count = 0
for i in range(2**N): #bit search
flag = True
for k in range(M): #Find out about all light bulbs
count = 0
for j in range(N): #Do for numbers with 1 flag in bit
if (i >> j) & 1:
count += lights[k][j]
if count % 2 != P[k]: #If even one light bulb does not match p, set flag to False and break
flag = False
break
if flag: #Clear all and increase count if flag is True
answer_count += 1
print(answer_count)
The problem statement is a little difficult to understand. Since it is difficult to handle how input is given, we devised a way to receive input and created a two-dimensional array with a light bulb on the vertical axis and a switch on the horizontal axis. In this array, 1 is set when each bulb and switch are connected, and 0 is set when they are not connected.
If this array is created, bit search can be done easily. The policy is
- Create a two-dimensional array of light bulbs and switches as described above
- For all switches, bit full search whether to turn on or off (realized by i and j of for statement)
- Check whether all the light bulbs are lit in each bit state (realized by k in the for statement)
- When checking whether the light bulb is lit or not, put the information with
`flag```, and whenflag``` becomes ``` False```, ``break``` - Count the number of states where
flagbecomes `` `True``` and that is the answer is.
012. AtCoder Beginner Contest 002 D-Faction
Answer
import itertools
N, M = map(int, input().split()) #N is the number of members, M is the number of relationships
members = list(range(N))
relation = [[0] * N for _ in range(N)] #Relationship matrix
for _ in range(M):
x, y = map(int, input().split())
x -= 1
y -= 1
relation[x][y] = 1
relation[y][x] = 1
max_answer = 0
for group_num in range(1, N+1): #Try all the people in the group
temp_answer = 0
for c in itertools.combinations(members, group_num): #List a specific number of members
flag = True
for base_c in c: #People who check relationships
for check_c in c: #Members to be checked
if base_c == check_c: #Don't check myself
continue
if relation[base_c][check_c] == 0: #Break immediately if there is no relationship
flag = False
break
if not flag:
break
if flag: #OK only when flag is True
temp_answer = group_num
max_answer = max(max_answer, temp_answer)
print(max_answer)
I couldn't do it without using itertools, so I had no choice but to use itertools.I used combinations.
The code is a little complicated, but what I'm doing is simple:
1. ```N```Any number of people to extract from the members of the Diet```group_num``To specify. This 1~I will do all the way up to N people
2. ```N```person's```members```From```group_num```List all the cases to extract people
3.Each member(```base_c```)About the members extracted in 2 above(```check_c```)Check if you know
4.Be careful not to check yourself when checking, and if you don't get acquainted, immediately```break```I will do
5.All lawmakers(```base_c```)When it is judged that there is an acquaintance relationship in(```flag==True```)Is that```group_num```Is a candidate for the answer
6. 1~Repeat 6```group_num```Maximum value is the answer
is.
---
### 013. [JOI 2008 Qualifying 5-rice cracker](https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_e)
####Answer
```python
import numpy as np
R, C = map (int, input (). split ()) # R: vertical, C: horizontal
grid = np.array([list(map(int, input().split())) for _ in range(R)])
max_answer = 0
for i in range(2**R):
copy_grid = grid.copy () # Make a copy as it will rewrite the matrix
for row in range(R):
if (i >> row) & 1: # Perform bit search for a small number of row directions
copy_grid [row,:] = copy_grid [row,:] ^ 1 # Invert 0,1 by bit operation
col_sum = copy_grid.sum (axis = 0) # Find the sum of each column
for col in range(C):
if col_sum [col]> = R // 2 + 1: # 1 Turn over where there are many
copy_grid[:, col] = copy_grid[:, col] ^ 1
answer = R * C - copy_grid.sum()
max_answer = max(max_answer, answer)
print(max_answer)
As you can see in the hint, the upper limit of R is small, so search R completely and make fine adjustments on the C side. The policy is 1.Try all the places to turn over in the R direction 2.After turning over in the R direction, as a fine adjustment in the C direction, turn over only the part where there are many rows that are 1. 3.Count the number of 0s in the resulting matrix(The whole square-total) 4.The answer is the one that takes the maximum of each counted result
is.
The method of converting 0 to 1 and 1 to 0, which is an operation to turn over, is a bit operation.^1Is used.
014. Square869120Contest #4 B - Buildings are Colorful!
####Answer
import itertools
N, K = map (int, input (). split ()) # N is the number of buildings, paint more than K color
A = list(map(int, input().split()))
N_index = list (range (1, N)) # Because the leftmost is fixed
min_cost = float('inf')
for target_indexes in itertools.combinations (N_index, K-1): Try all the ways to select K-1 from #N_index
cost = 0
copy_A = A.copy()
for i in target_indexes:
if copy_A[i] <= max(copy_A[:i]):
diff = max (copy_A [: i]) --copy_A [i] # For the target building, make it 1 larger than max of the building to the left of it
copy_A[i] += diff + 1
cost += diff + 1
min_cost = min(min_cost, cost)
print(min_cost)
The policy is
1.The leftmost building is fixed
2.From the second building onwardsK-1Try all the way to choose
3.Index of the selected buildingtarget_indexes Store in and check the height of each building
4.buildingiIs the maximum height of the building before that+Building to be 1iAdjust the height of thecostAggregate as
5.After doing all the abovecostThe answer is the one that takes the minimum value of
is.
Recommended Posts