** Aim for a light blue coder! !! !! !! !! !! ** **

So [Guidelines for improving AtCoder, a competition pro taught by Red Coder [Intermediate Edition: Aim for Light Blue Coder! ]]( https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7 % B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% E5% 8E % BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F) (@ e869120)

AtCoder has collected 100 good educational questions that are appropriate for brown and green coders to achieve a light blue coder, or rating 1200, with a small number of questions.

100 past questions that beginners and intermediates should solve in this article` Will be solved with ** Python **! Thanks to @ e869120! !! !! !! !! !!

Past article link

** Search all: List all ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part1 / 22] ** Full search: All enumeration to reduce the number of streets by devising ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part2 / 22] ** Full search: Bit full search ** [[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Full search: Permutation full search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part4 / 22] ** Binary search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part5 / 22] ** Depth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part6 / 22] ** Breadth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]

** (Added on 2020/05/07) **

Supplement Enter from the (** Part 6 **) article in this 100-question series input()→sys.stdin.readline().rstrip() I'm changing to! [Python] Competitive template [At Coder] I also made an article for the template, so please use it if you like ~

"Part 3" ~ Bit full search ~

We will solve the following 5 questions!

Full search: Bit full search

10 ALDS_5_A --Brute force is a basic problem. 11　AtCoder Beginner Contest 128 C - Switches 12 AtCoder Beginner Contest 002 D-Faction 13 JOI 2008 Qualifying 5-Osenbei It is a little difficult for brown coder, but it is recommended to solve it. 14 Square869120Contest # 4 B --Buildings are Colorful! It is a difficult problem that cannot be solved easily, but if you solve it, you will definitely gain strength.

10 ALDS_5_A-Brute force

** We have independently developed the strongest template for bit full search! bit = [i>>j&1 for j in range(N)]** With this template No matter what bit full search comes ** I'm not scared of anything anymore **

`test.py`


def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
A = LI()
q = I()
m = LI()
ans = 0
partial_sum = set()
for i in range(2**n):
    bit = [i>>j&1 for j in range(n)] #Strongest template
    partial_sum.add(sum([A[k]*bit[k] for k in range(n)]))
for x in m:
    print('yes' if x in partial_sum else 'no')

** (Added on 2020/05/04) **
Another solution
You can also solve it with ** DFS **! It's like searching all the way to the end to add or not add the next digit! The point is to set the index and sum ** and store them on the stack! !! !!

** ◆ Recursive Ver **

`test.py`


def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
A = LI()
q = I()
m = LI()
partial_sum = set()
def dfs(i,_sum):
    if i==n:
        partial_sum.add(_sum)
        return
    dfs(i+1,_sum)
    dfs(i+1,_sum+A[i])
dfs(0,0)
for x in m:
    print('yes' if x in partial_sum else 'no')

** ◆ Stack Ver **

`test.py`


def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
A = LI()
q = I()
m = LI()
partial_sum = set()
stack = [] #Put index and sum
def dfs():
    stack.append([0,0])
    stack.append([0,A[0]])
    partial_sum.add(A[0])
    while stack:
        i,s = stack.pop()
        i += 1
        if i==n:
            partial_sum.add(s)
            continue
        stack.append([i,s])
        stack.append([i,s+A[i]])
dfs()
for x in m:
    print('yes' if x in partial_sum else 'no')

By the way, the execution time is also faster with ** DFS ** ~ Test case for n, q = (20,200) Measurement result with the above code!

-** Bit full search : 6.81 seconds - DFS (Recursion Ver) : 0.54 seconds - DFS (Stack Ver) **: 1.03 seconds

11　AtCoder Beginner Contest 128 C - Switches Difficulty:807 ** The strongest template for bit full search is a big success! ** ** The problem statement is a little complicated, but I'll do my best to understand it while looking at the input / output examples. Since there are a maximum of 10 switches, it seems that we can search all bits (computational complexity)! If you can make a policy, you can solve this problem! !! !! ** I'm not scared of anything anymore **

`test.py`


def LI(): return list(map(int,input().split()))
N,M = LI()
ks = [LI() for _ in range(M)]
p = LI()
ans = 0
for i in range(2**N):
    bit = [i>>j&1 for j in range(N)]
    for k,x in enumerate(ks):
        _,*s = x
        if p[k] != sum([bit[y-1] for y in s])%2:
            break
    else:
        ans += 1
print(ans)

12 AtCoder Beginner Contest 002 D-Faction

** Difficulty: 1405! !! !! Finally the problem of light blue level! !! !! ** ** ** I couldn't solve it at first sight! ** ** In addition to full bit search, it may be easier to solve if you have knowledge of ** graphs. ** ** The idea of graphs is also related to DFS and BFS, so I want to master it! !! !!

Kenchon's article DFS (Depth-first Search) Super Introduction! ~ Entrance to the world of graph algorithms ~ [Part 1]

Think as follows!

Represent human relationships in an undirected graph.
Are each member of parliament in a faction in a bit full search? Think about all the ways that it is not included. For each of 3.2, if everyone has a relationship with each other, a candidate for an answer!

`test.py`


import itertools
def LI(): return list(map(int,input().split()))
N,M = LI()
xy = [LI() for _ in range(M)]
ans = 1
graph = {i:[] for i in range(1,N+1)} #1_indexed
for a in xy:
    x,y = a
    graph[x].append(y)
    graph[y].append(x)
for i in range(2**N):
    bit = [i>>j&1 for j in range(N)]
    giinsuu = sum(bit)
    if giinsuu<=1:
        continue
    giinNO_bit1 = [k+1 for k in range(N) if bit[k]==1]
    for b,c in itertools.product(giinNO_bit1,repeat=2):
        if b==c:
            continue
        if not b in graph[c]:
            break
        if not c in graph[b]:
            break
    else:
        ans = max(ans,giinsuu)
print(ans)

With a detailed supplement to the code,

for b,c in itertools.product(giinNO_bit1,repeat=2):
    if b==c:
        continue
    if not b in graph[c]:
        break
    if not c in graph[b]:
        break
else:
    ans = max(ans,giinsuu)

ʻThe previous article on how to use itertools.product and for / else` [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part2 / 22] Since it is explained briefly in, please refer to this as well ...

Also, the image of the if statement is a past article [Python] ABC133B (upper right triangle problem) [At Coder] An image of calculating all the upper right triangle and lower left triangle in the table that appears in this article! !! !! If you have an image of this table, I think you can even code it!

13 JOI 2008 Qualifying 5-Osenbei

** I couldn't solve it at first sight! !! It may be easier to solve if you have knowledge of Numpy and XOR (exclusive OR ^). ** **

Numpy When dealing with data of 2D array or more, the logic is easy to understand because the code is not complicated --XOR (operator: ^) What can be represented by " 0 or 1 "seems to be compatible when performing the operation" 0 ⇄ 1" ( 0 ^ 1 → 1, 1 ^ 1 → 0)

I thought when I saw the AC code of amazing people.

Think as follows!

Examine all patterns of flipping / not flipping all lines 2.1 Count the number of 1s in each column for each pattern (= black) In 3.2, we can ship 0 number => that is, R-black. However, since the line can also be turned over The larger of R-black and black! The answer is the sum of all the results in each column!

The count of the number of 1s in each column can be answered by adding each column. (Addition of each column is the 18th of Numpy!)

`test.py`


import numpy as np
def LI(): return list(map(int,input().split()))
R,C = LI()
a = np.array([LI() for _ in range(R)])
ans = 0
for i in range(2**R):
    bit = np.array([[i>>j&1 for j in range(R)]]).T
    black = (a^bit).sum(axis=0)
    ans = max(ans,np.fmax(R-black,black).sum())
print(ans)

It was an unexpectedly short code!

With a detailed supplement to the code,

bit = np.array([[i>>j&1 for j in range(R)]]).T

T is transposed, but [This site] (https://deepage.net/features/numpy-transpose.html) Therefore, it will not be effective unless the target of transposition is two-dimensional or more! The target of transposition is one-dimensional np.array([i>>j&1 for j in range(R)]).T Then no.

Use one of the following writing styles. Any one is fine!

np.array([[i>>j&1 for j in range(R)]]).T
np.matrix([i>>j&1 for j in range(R)]).T
np.array([i>>j&1 for j in range(R)]).reshape(R,-1)
np.array([[i>>j&1] for j in range(R)])

black = (a^bit).sum(axis=0)

ʻA ^ bitlooks like this ~ <img width="257" alt="スクリーンショット 2020-05-01 14.10.15.png " src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183481/cd40dd9d-5b1b-898f-6413-4bec36a8506b.png "> If you useXOR (operator: ^)with1`, it will turn over! !! !! !! !! In the example above, only the top line is flipped over! The bottom line remains the same! ** Wow! !! !! !! !! !! ** **

To count the number of 1s in each column, add up each column. Addition of each column can be added with ʻaxis = 0! For ʻaxis, This article Was easy to understand!

ans = max(ans,np.fmax(R-black,black).sum())

R-black looks like this ~ スクリーンショット 2020-05-01 14.41.21.png In terms of image, the following two are the same!

2 - [2 0 1 0 2] = [0 2 1 2 0]
[2 2 2 2 2] - [2 0 1 0 2] = [0 2 1 2 0]

For np.fmax, [This site] (https://note.nkmk.me/python-numpy-maximum-mimimun-fmax-fmin/) Was easy to understand!

** Conclusion! Numpy and XOR are amazing! !! !! !! !! !! ** **

14　Square869120Contest #4 B - Buildings are Colorful! ** It seemed to be solved at first glance, but I couldn't solve it! !! !! I'm sorry! ** ** Even when bit is 0, I didn't notice the pattern that the height of the building kijun increases ...

But if you can understand all the problems of bit full search so far, the idea itself is not so difficult!

`test.py`


def LI(): return list(map(int,input().split()))
N,K = LI()
a = LI()
ans = float('INF')
for i in range(2**(N-1)):
    bit = [i>>j&1 for j in range(N-1)]
    if K-1!=sum(bit):
        continue
    cost,kijun = 0,a[0]
    for k in range(N-1):
        if bit[k]==0:
            kijun = max(kijun,a[k+1])
            continue
        if a[k+1]>=kijun+1:
            kijun = a[k+1]
            continue
        cost += (kijun+1)-a[k+1]
        kijun += 1
    ans = min(ans,cost)
print(ans)

Next time, I will solve the following 3 questions!

Full search: Permutation full search

15　AtCoder Beginner Contest 145 C - Average Length 16　AtCoder Beginner Contest 150 C - Count Order 17 ALDS_13_A -8 Queens problem is interesting.

Part3/22 end!

Next (Part 4/22)