Pythonで解く【初中級者が解くべき過去問精選 100 問】(015 - 017 全探索：順列全探索)

# 1. 目的
[初中級者が解くべき過去問精選 100 問](https://qiita.com/e869120/items/eb50fdaece12be418faa)をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。

本記事は「015 - 017 全探索：順列全探索」です。

# 2. 総括
順列系の問題では```itertools```をうまく使うと解ける場合が多いです。
```permutaions```と```combination```と```product```はよく使うので、この辺はいろいろサンプルデータで試しながら学びました。


# 3. 本編

## 015 - 017 全探索：順列全探索

### 015. [AtCoder Beginner Contest 145 C - Average Length](https://atcoder.jp/contests/abc145/tasks/abc145_c)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/e311e1b8-3939-4338-b3de-de8dadb222fe.png)

#### 回答
```python

N = int(input())
towns = [tuple(map(int, input().split())) for _ in range(N)]

total_distance = 0
count = 0
for start in range(N-1):
    for end in range(start+1, N):
        start_x, start_y = towns[start]
        end_x, end_y = towns[end]

        total_distance += ((end_x - start_x)**2 + (end_y - start_y)**2)**0.5
        count += 1

# factor = math.factorial(N) とすると
# answer = total_distance * (factor * (N - 1) / count) / factor となり下記に式変形可能
answer = total_distance * ((N - 1) / count)
print(answer)

```
こちら計算方法がいろいろあります。
愚直にやると```permutation```ですべての並べ方列挙して全てにおいて距離を求めてその平均をとります。
これでも通ると思いますが、もう少し計算量を落とした回答としてみました。
方針は、
1. すべての2点の組み合わせの距離を合計する
2. この合計に```(N - 1) / 組み合わせの数```を乗じたものが答え

です
上記2については、コードにコメントとして残した式変形から導きだしています。

---

### 016. [AtCoder Beginner Contest 150 C - Count Order](https://atcoder.jp/contests/abc150/tasks/abc150_c)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/e9a4486c-f3b2-b2a2-41aa-cbcb6cbcefbd.png)

#### 回答
```python
import itertools

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

count = 1
for p in itertools.permutations(range(1, N+1)):

    if p == P:
        count_P = count
    if p == Q:
        count_Q = count

    count += 1

ans = abs(count_P - count_Q)
print(ans)

```
pythonの```itertools.permutations```が辞書順に列挙してくれることを信じて（！）愚直に書きます。
方針は、
1. 1~Nまでの順列を```itertools.permutations```で列挙
2. 列挙するカウントを数えて置き、P、Qに一致したところで```count_P```と```count_Q```を記録
3. 両者の差をとったものが答え

です。
```itertools```がない場合はもうちょっと考えなければいけないと思いますが、便利なので何も考えずに使用しました。

---

### 017. [ALDS_13_A - 8 クイーン問題](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_A&lang=ja)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/96129141-93c1-d43e-7ee5-a548cbe20324.png)

#### 回答
```python

import itertools
import copy

def flag_queen_load(grid, r, c):
    for i in range(1, 8):
        if 0 <= c+i and c+i < 8:
            grid[r][c+i] = -1 #右
        if 0 <= c-i and c-i < 8:  
            grid[r][c-i] = -1 #左
        if 0 <= r+i and r+i < 8:  
            grid[r+i][c] = -1 #下
        if 0 <= r-i and r-i < 8:
            grid[r-i][c] = -1 #上
        if 0 <= r-i and r-i < 8 and 0 <= c+i and c+i < 8:
            if grid[r-i][c+i] == 9:
                continue
            grid[r-i][c+i] = -1 # 右上
        if 0 <= r+i and r+i < 8 and 0 <= c+i and c+i < 8:
            if grid[r+i][c+i] == 9:
                continue
            grid[r+i][c+i] = -1 # 右下
        if 0 <= r+i and r+i < 8 and 0 <= c-i and c-i < 8:  
            if grid[r+i][c-i]  == 9:
                continue
            grid[r+i][c-i] = -1 # 左下
        if 0 <= r-i and r-i < 8 and 0 <= c-i and c-i < 8:
            if grid[r-i][c-i] == 9:
                continue
            grid[r-i][c-i] = -1 # 左上

    grid[r][c] = 9 # 自分自身

    return grid


if __name__ == "__main__":

    k = int(input())
    grid = [[0] * 8 for _ in range(8)]
    for _ in range(k):
        r, c = map(int, input().split())
        grid = flag_queen_load(grid, r, c)

    # 0~7の番号を順列を全通り試す
    # 生成される順列について、添え字は行番号、要素は列番号として考える
    for perm in itertools.permutations(range(8)):
        copy_grid = copy.deepcopy(grid) # 毎回新しいgridを使う
        count = 0
        for row, col in enumerate(perm):
            if copy_grid[row][col] == -1:
                break
            if copy_grid[row][col] == 9:
                continue
            
            copy_grid[row][col] = 9
            copy_grid = flag_queen_load(copy_grid, row, col)
            count += 1

        if count == 8 - k: # 8-k個のクイーンをおけたらbreak
            break
    
    # 答え表示
    for row in range(8):
        for col in range(8):
            if copy_grid[row][col] == -1:
                print('.', end='')
            else:
                print('Q', end='')
        print()

```
もともとはNumpyで書いていたのですがAOJはNumpy使えないのでしょうか？エラーとなって提出できなかったので普通のリストで書き直しました。
方針は、
1. まずはチェス盤を```grid```とし、クイーンがある位置を9、クイーンが襲撃できる箇所を-1、それ以外の空白の個所を0とします
2. ある座標```(r, c)```にクイーンを置いた際に盤面を更新する関数```flag_queen_load()```を作成しておきます
3. あとはすべての置き方を試して、うまく置けるかを判定します
4. 全通り試すにあたっては```itertools.permutations(range(8))```で0~7の順列を列挙し、生成される順列について、添え字は行番号、要素は列番号として考えます
5. あとは、盤面が-1の場合は置けないので```break```し、9の場合はOKなので```continue```します
6. 新たにクイーンを```8-k```回置ける時が答え

です。

関数```flag_queen_load()```が汚いのでもうちょっときれいに書けばよかったです。




---