【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】

**目指せ水色コーダー！！！！！！**

ということで、 
[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](
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 で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。

こちらの記事の`初中級者が解くべき過去問精選 100 問`
を**Python**で解いていきます！
@e869120さんに感謝！！！！！！

###過去記事リンク
**全探索：全列挙**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】](https://qiita.com/rudorufu1981/items/8ae8beeba7b047f2687c)
**全探索：工夫して通り数を減らす全列挙**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】](https://qiita.com/rudorufu1981/items/282e06a6898f021b5e7f)
**全探索：ビット全探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】]
(https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f)
**全探索：順列全探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/22】](https://qiita.com/rudorufu1981/items/71abd5320a636e9146cb)
**二分探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part5/22】](https://qiita.com/rudorufu1981/items/2683c3988b246c9cf9ce)
**深さ優先探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】](https://qiita.com/rudorufu1981/items/e39aa16d73615c7e589f)
**幅優先探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part7/22】](https://qiita.com/rudorufu1981/items/4804987152ad22f3fcb4)

**(2020/05/07 追記)**
※補足
この100問解いてみたシリーズの(**Part6**)の記事から、入力を
`input()`→`sys.stdin.readline().rstrip()`
に変えています！
[【Python】競プロテンプレ【AtCoder】](https://qiita.com/rudorufu1981/items/c6bc5e4d72cfe1cb7f14)
テンプレ用の記事も作ったので、よかったら使ってください〜

#「Part3」〜ビット全探索編〜
以下の5問を解いていきます！

>
#####全探索：ビット全探索
10　ALDS_5_A - 総当たり　基本問題です。
11　AtCoder Beginner Contest 128 C - Switches
12　AtCoder Beginner Contest 002 D - 派閥
13　JOI 2008 予選 5 - おせんべい　茶色コーダーにはやや難問ですが解くことをおすすめします。
14　Square869120Contest #4 B - Buildings are Colorful!　工夫も必要で、一筋縄では解けない難問ですが、解けば確実に力がつきます。


#[10　ALDS_5_A - 総当たり](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja)
**ビット全探索の最強テンプレを独自開発しました！
`bit = [i>>j&1 for j in range(N)]`**
このテンプレを使えば、
どんなビット全探索がきても
**もうなにも怖くない**

```python: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)] #最強テンプレ
    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')
```
**(2020/05/04 追記)**
＜別解＞
**DFS**でも解けます！
次の桁を足すか、足さないか、を最後まで全探索する感じです！
**インデックスと和をセット**、でスタックに貯めるのがポイント！！！


**◆再帰Ver**

```python: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')
```
**◆スタックVer**

```python: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 = [] #indexと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')
```
※ちなみに実行時間も**DFS**の方が早いです〜
`n,q=(20,200)`のテストケース
上のコードでの計測結果！

- **ビット全探索**：6.81秒
- **DFS(再帰Ver)**：0.54秒
- **DFS(スタックVer)**：1.03秒

#[11　AtCoder Beginner Contest 128 C - Switches](https://atcoder.jp/contests/abc128/tasks/abc128_c)
Difficulty:807
**ビット全探索の最強テンプレが大活躍！**
問題文は少し複雑だけど、入出力例も見ながら頑張って理解して、
スイッチは最大10個なので(計算量的に)ビット全探索でいけそう！
と方針さえ立てられたらこの問題も解ける！！！
**もうなにも怖くない**

```python: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 - 派閥](https://atcoder.jp/contests/abc002/tasks/abc002_4)
**Difficulty:1405！！！ついに水色レベルの問題！！！**
**初見で解けませんでした！**
ビット全探索の他に、**グラフの知識があると解きやすいかも。**
グラフの考えはDFSやBFSにも関わってくるので、マスターしておきたい！！！
※けんちょんさんの記事
[DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】](
https://qiita.com/drken/items/4a7869c5e304883f539b)

以下のように考える！
1.人間関係を無向グラフで表す。
2.ビット全探索で、それぞれの国会議員が派閥に入っているか？入っていないかの全通り考える。
3.2のそれぞれについて、全員互いに人間関係があれば答えの候補！

```python: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)
```
コードの細かい補足をすると、

```python
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)
```

`itertools.product`と`for/else`の使い方については、前回の記事
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】](https://qiita.com/rudorufu1981/items/282e06a6898f021b5e7f)
で簡単に解説しているので、こちらもあわせてご参考に・・・

また、if文のところのイメージは、過去記事
[【Python】ABC133B(右上三角形問題)【AtCoder】](https://qiita.com/rudorufu1981/items/0d6d6e657864dc09ee47)
この記事に出てくる表の`右上三角形`と`左下三角形`をすべて計算していくイメージ！！！
この表のイメージが持てたら、コードもすらすらかけると思う！

#[13　JOI 2008 予選 5 - おせんべい](https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_e)
**初見で解けませんでした！！
`Numpy`と`XOR`(排他的論理和 `^`)の知識があると解きやすいかも。**

- `Numpy`
　2次元配列以上のデータを扱う時に、コードが複雑にならないのでロジックがわかりやすくなる
- `XOR(演算子：^)`
「`0 or 1`」で表せるものは「`0⇄1`」という操作をするときに相性良さそう(`0^1→1、1^1→0`)

と、すごい人たちのACコードを見て思いました。

以下のように考える！
1.すべての行のひっくり返す/ひっくり返さないの全パターンを調べる
2.1のそれぞれのパターンに対し各列の`1`の数をカウント`(=black)`
3.2で出荷できるのは、`0`の数=>つまり`R-black`。
ただし、列もひっくり返せるので
`R-black`と`black`の大きいほう！の各列の結果をすべて足したものが答えの候補！

各列の`1`の数のカウントは、各列を足し算すれば答えが出る。
（各列の足し算とかは`Numpy`の十八番！）

```python: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)
```
案外短いコードだった！

コードの細かい補足をすると、

```python
bit = np.array([[i>>j&1 for j in range(R)]]).T
```
`T`は転置してくるものであるが、
[こちらのサイト]
(https://deepage.net/features/numpy-transpose.html)
より、転置の対象が2次元以上でないと効果を発揮してくれない！
転置の対象が1次元
`np.array([i>>j&1 for j in range(R)]).T`
ではだめ。

以下のいずれかの書き方でかける。どれでもいい！

- `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)])`

```python
black = (a^bit).sum(axis=0)
```
`a^bit`は、こんな感じ〜
<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">
`1`との`XOR(演算子：^)`を使えば、ひっくり返る！！！！！
上の例だと、上の行だけひっくり返っている！下の行はそのまま！
**すごい！！！！！！**

各列の`1`の数のカウントは、各列を足し算すればいい。
各列の足し算は、`axis=0`で足し算できる！
`axis`については、
[こちらの記事](https://qiita.com/shuetsu@github/items/2bf8bba233c5ecc7a0ad)
がわかりやすかった！

```python
ans = max(ans,np.fmax(R-black,black).sum())
```
`R-black`は、こんな感じ〜
<img width="248" alt="スクリーンショット 2020-05-01 14.41.21.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183481/7842782e-30de-22b7-b16d-a07e18b8bc3e.png">
イメージ的には、以下の2つは一緒！

- `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]`

`np.fmax`については、
[こちらのサイト]
(https://note.nkmk.me/python-numpy-maximum-mimimun-fmax-fmin/)
がわかりやすかった！

**結論！
`Numpy`と`XOR`はすごい！！！！！！**


#[14　Square869120Contest #4 B - Buildings are Colorful!](https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b)
**初見で解けそうだったけど、解けなかった！！！
くやしい！**
`bit`が0のときも、建物の`kijun`の高さが増えていくパターンに気付けなかった・・・

でもこれまでのビット全探索の問題がすべて理解できれば、考え方自体はそこまで難しい問題ではない！

```python: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)
```

次回は、以下の3問を解いていきます！
>
#####全探索：順列全探索
15　AtCoder Beginner Contest 145 C - Average Length
16　AtCoder Beginner Contest 150 C - Count Order
17　ALDS_13_A - 8 クイーン問題　面白いです。


Part3/22
おわり！

[次(Part4/22)へ](https://qiita.com/rudorufu1981/items/71abd5320a636e9146cb)