【AtCoder】ABC190-194のCをPython3で解説

## ABC190 C - Bowls and Dishes

https://atcoder.jp/contests/abc190/tasks/abc190_c

### タイプ

- 全探索（bit全探索）
- ライブラリ
- set()

### 解説
工夫して解く全探索問題。
問題文が少し理解しにくいと思うが、いってしまえばこうだ。
**「C, Dのどちらかを選んで組み合わせた4つの数が、各A, Bの条件にどれだけ当てはまるか」**ということだ。

これでもわかりにくいと思うので、サンプル入力を参考にして解説していく。

```python
4 4
1 2
1 3
2 4
3 4
4
3 4
1 2
2 4
2 4
```

入力の部分の解説は省く。
問題は`for balls in product(*choice)`からである。

まず、`*`はかんたんにいうと、**大枠の括弧を外す操作**である。
例えば、このときの`choice`は、`[(3, 4), (1, 2), (2, 4), (2, 4)]`である。つまり、`*choice`は、`(3, 4) (1, 2) (2, 4) (2, 4)`となる。

次に、`product()`。これは事前に`from itertools import product`しなければならない。この操作をすると全組み合わせを試すことができる。
例えば、`product(*choice)`と書くと、各タプルのインデックス`0`の値を持ってくるので、`(3, 1, 2, 2)`となる。このように`(3, 1, 2, 4)`、`(3, 1, 4, 2)`、`(3, 1, 4, 4)`...と後ろから一つずつ値を変えていく。

これらを`balls`に入れていくわけだが、次の操作として`set()`で重複をなくしておく。

そして、`cond`にいれた`A`と`B`のそれぞれの値が`set(balls)`のなかにあるかを確認する。このとき`A`と`B`どちらの値も`set(balls)`に存在して、初めて条件を満たす。つまり、コードでは`A in balls and B in balls`と書ける。条件を満たした数だけ`sum()`して、`cnt`に代入。これをループで回していくので、条件を満たしている数が多いものを随時更新するために、`if ans < cnt:`が必要である。

### 回答例

```python
# 全探索
from itertools import product

N, M = map(int, input().split())

cond = []
choice = []

# 皿A, 皿B
for _ in range(M):
    A, B = map(int, input().split())
    cond.append((A, B))

# K人
K = int(input())

# 皿C, 皿D
for _ in range(K):
    C, D = map(int, input().split())
    choice.append((C, D))

ans = 0

# *choice -> ( , ) ( , ) ( , ) ( , )
# 各タプルからどちらかをとりだしballsに代入

for balls in product(*choice):
    # set()で重複を削除
    balls = set(balls)

    # set(balls)の中で、A,B両方の値が存在したら条件を満たしているので、1カウント
    cnt = sum(A in balls and B in balls for A, B in cond)

    # 条件を満たしているものが、多いものをansに更新
    if ans < cnt:
        ans = cnt

print(ans)

```

## ABC191 C - Digital Graffiti
https://atcoder.jp/contests/abc191/tasks/abc191_c

### タイプ

- 全探索
- 二次元配列

### 解説
問題を見てもらった方は分かる通り、「サンプル数少なすぎ問題」。
少し例を出すと、

```python
.....
.###.
.###.
.###.
.....
```

これは四角形。

```python
.....
.###.
.###.
.##..
.....
```

右下が欠けたこれは、六角形。
「ん？六角形？」と思うかもしれないが、みなさんが想像している蜂の巣のような六角形ではない。「角が６つあるもの」を今回は六角形とよんでいる。「じゃあ、#にも角があるじゃないか」というと元も子もないが。

そんなわけで、こういう定義で話を進めていく。

**これを求めるには全探索して角を求めることが必要である。**ここで角の条件とは、2×2を縦横シフトさせ、4ブロック中 1 or 3 ブロックがあれば、角となります。

4ブロック中1ブロックが角とはなにか。

たとえば、最初のサンプルでいえば次のようになる。

```python
# 2×2

..
.#

# 右下'#'の左上が角
```

2番目のサンプルでいえば次のようになる。

```python
# 2×2

##
#.

# 右上'#'の右下が角
```

このように2×2のブロックでシフトさせていき、角の数を数える。

まず、`table`に高さ`H`だけ文字列（ . or # ）を追加。
これを行と列についてforループ。2×2のブロックを二次元配列で調査し、'#'の数に応じて、先程述べたように`ans`に1を加える。

### 回答例
```python
# 全探索
H, W = map(int, input().split())
table = []

for _ in range(H):
    S = input()
    table.append(S)

ans = 0

for row in range(H-1):
    for col in range(W-1):
        A = [''] * 4
        A[0] = table[row][col]
        A[1] = table[row+1][col]
        A[2] = table[row][col+1]
        A[3] = table[row+1][col+1]

        if A.count('#') == 1 or A.count('#') == 3:
            ans += 1

print(ans)
```

## ABC192 C - Kaprekar Number

https://atcoder.jp/contests/abc192/tasks/abc192_c

### タイプ
- 関数（def( )）

### 解説
問題文のとおりにやれば解ける問題。

注意点は、`int(''.join(sorted(s)))`。文字列をソートすると勝手に昇順に並び替えてくれる。
これを`ans`にいれて、`K`回ループを回せばよい。

### 回答例
```python
# 関数

def func(x):
    s = str(x)

    g1 = int(''.join(sorted(s, reverse=True)))
    g2 = int(''.join(sorted(s)))
    return g1 - g2

N, K = map(int, input().split())

ans = N
for _ in range(K):
    ans = func(ans)

print(ans)
```

## ABC193 C - Unexpressed

https://atcoder.jp/contests/abc193/tasks/abc193_c

### タイプ

- 全探索（細工あり）
- set()

### 解説
1以上N以下の整数のうち、2以上の整数a, bを用いて$a^b$とあらわせないものはいくつあるか。
あらわせないものが、あらわせるものよりも圧倒的に多いので、Nからあらわせるものを引いた値を出力すれば良い。

また、全探索する数は`N`の1/2乗に書き換える。なぜなら、bが2以上で結局forで2乗するので、それ以上の探索が必要ないからである。

`for`でaを+1ずつ回し、whileで毎回aかけてあげることで、$a^b$が実装される。

`set()`を使っているのは、値が重複しないようにするためである。今回探したいのは、1以上N以下の整数なので、追加する値は重複してはならない。つまり、`set()`で管理している。

### 回答例
```python
N = int(input())
sq = int(10**5)
S = set()

for a in range(2, sq + 1):
    cur = a ** 2
    while cur <= N:
        S.add(cur)
        cur *= a

print(N - len(S))
```

## ABC194 C - Squared Error

https://atcoder.jp/contests/abc194/tasks/abc194_c

### タイプ

- 制約を活用
- `from collections import Counter`

### 解説
そのまま計算すると、$O(N^2)$でTLEになる。

この数列の特徴は、「2乗しているので結果が変わらない」ということである。
したがって、各数字が何回でるかをカウントしてあげるだけでいい。

制約は、$|A_i|<=200$より、-200~200の401種類。

`Counter(A)`でどの数がどのくらいあるのかを辞書型で保存する。これを`cnt`に代入して、組み合わせたい数字`x`と`y`を、`cnt[x]`と`cnt[y]`でどのくらいの数があるか探す。
`(x - y)**2`で同じ数がでるので、これが何通りずつあるかを数え上げて、`total`にいれる。
これを`x <= y <= 200`となるように、forループを回す。

### 回答例
```python
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
cnt = Counter(A)

ans = 0

for x in range(-200, 200+1):
    for y in range(x+1, 200+1):
        xcnt = cnt[x]
        ycnt = cnt[y]
        total = xcnt * ycnt * (x - y) ** 2
        ans += total

print(ans)
```

## 編集後記
これから190番台から下ってC問題の解説記事を出していきますので、お見逃しなく.


＜参考文献＞
- https://qiita.com/u2dayo
- https://atcoder.jp/home