【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/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)
テンプレ用の記事も作ったので、よかったら使ってください〜

#「Part4」〜順列全探索編〜
以下の3問を解いていきます！

>
#####全探索：順列全探索
15　AtCoder Beginner Contest 145 C - Average Length
16　AtCoder Beginner Contest 150 C - Count Order
17　ALDS_13_A - 8 クイーン問題　面白いです。

#[15　AtCoder Beginner Contest 145 C - Average Length](https://atcoder.jp/contests/abc145/tasks/abc145_c)
Difficulty:297
`Numpy`使わなくても全然いいけど、せっかく使い方覚えてきたので、
積極的に使っていくスタイル。

**順列は`itertools.permutations`こいつ使ってあげればOK！**
`(0,1,2)`：町0→町1→町2
`(0,2,1)`：町0→町2→町1
`(1,0,2)`：町1→町0→町2
...
と考える。


```python:test.py
import itertools,math,numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
xy = np.array([LI() for _ in range(N)])
sum_norm = 0
dict_norm = {}
for a in itertools.permutations(range(N)):
    for i in range(len(a)-1):
        vector = tuple(xy[a[i+1]]-xy[a[i]])
        if not vector in dict_norm:
            dict_norm[vector] = np.linalg.norm(vector)
            vector_inverse = tuple(xy[a[i]]-xy[a[i+1]])
            dict_norm[vector_inverse] = dict_norm[vector]
        sum_norm += dict_norm[vector]
print(sum_norm/math.factorial(N))
```
`tuple`で囲っているのは、辞書型のキーは`hashable`でないとエラーになるため！
※参考(過去記事)
[【Python】JOI 2007 本選 3 - 最古の遺跡(①高校数学ベクトル、②「in リスト」は激遅)【AtCoder】](https://qiita.com/rudorufu1981/items/071aaf6eaccdce2e4295)

`np.linalg.norm(vector)`
こいつはいい感じにベクトルの距離だしてくれる!


逆ベクトルも距離は同じなので、辞書に入れてやる。

＜別解＞
数学がそこそこ得意な人はこんな解法も！
（順列全探索の話ではなくなりますが・・・）

`N=n`の一般解を(ノートとペンを使って)頑張って見つけることができれば、計算量は激減！！！
![IMG_2736.JPG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183481/a4c1d370-aaac-0fa7-e4a9-a3f32a0e9501.jpeg)
`N=n`の一般解より、
答えは、異なる2点間の距離の和を2倍して`N`で割ればいい！

```python:test.py
import numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
xy = np.array([LI() for _ in range(N)])
sum_norm = 0
for i in range(N):
    for j in range(i,N):
        sum_norm += np.linalg.norm(xy[j]-xy[i])
print(2*sum_norm/N)
```

#[16　AtCoder Beginner Contest 150 C - Count Order](https://atcoder.jp/contests/abc150/tasks/abc150_c)
Difficulty:338
`itertools.permutations(range(1,N+1))`
こいつソートしてやろうと思ったら、すでに辞書順になってた！


```python:test.py
import itertools
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
P = LI()
Q = LI()
sequence = [list(x) for x in itertools.permutations(range(1,N+1))]
print(abs(sequence.index(P)-sequence.index(Q)))
```

#[17　ALDS_13_A - 8 クイーン問題](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_A&lang=ja)
**解けませんでした！
というかこの問題、初見で解ける人いるの？？？**
でも面白い問題でした〜
ググったら、Nクイーン問題という名前がついている有名な問題らしいです！

以下のように考える！
1.`itertools.permutations(range(8))`とそのインデックスのセットで、Qの8つの場所が一意に決まる！**8!パターン全探索！！！**
　ちなみに、この時点で**縦横の制約**はクリア！
2.1のそれぞれのパターンに対し、**斜めの制約**のチェック！
　これは知らないと無理w(詳しくは以下のACコードを見てくださいw)
　x+y,x-yがかぶっていたら、斜めラインに存在するのでNG！！！
　覚えましょう！この考え方は面白い！
3.2の**斜めの制約**もクリアしたものの中で、与えられているQがすべて含まれていればそれが答え！！！

```python:test.py
import itertools
def I(): return int(input())
def LI(): return list(map(int,input().split()))
k = I()
rc = [LI() for _ in range(k)]
for a in itertools.permutations(range(8)):
    XY = [[x,y] for x,y in enumerate(a)]
    if len(set([x+y for x,y in XY])) !=8 or len(set([x-y for x,y in XY])) !=8:
        continue
    count = 0
    for r,c in rc:
        if [r,c] in XY:
            count += 1
    if count !=k:
        continue
    board = [['.' for _ in range(8)] for _ in range(8)]
    for x,y in XY:
        board[x][y] = 'Q'
    break
for b in board:
    print(*b,sep='')
```

答えの可能性ではなくなった瞬間に`continue`とすることで、ネストを深くしないようにしています。
ネストが深くなったらコードがわかりずらくなる！
過去記事
[【リーダブルコード】内容を5つ抜粋！【競技プログラミング】]
(https://qiita.com/rudorufu1981/items/81f305b4686ab8cc5120)
より〜


次回は、以下の6問を解いていきます！
>
#####二分探索
18　ALDS_4_B - 二分探索　基本問題です。map でも解けますが二分探索で解いてみてください。
19　JOI 2009 本選 2 - ピザ
20　AtCoder Beginner Contest 077 C - Snuke Festival　面白いです。
21　AtCoder Beginner Contest 023 D - 射撃王　教育的に良いです。
22　AtCoder Regular Contest 054 B - ムーアの法則　微分して二分法をすると解けます。三分探索と話が繋がってくるので、それも調べてみると良いと思います。
23　JOI 2008 本選 3 - ダーツ　工夫して二分探索する、チャレンジ問題です。


Part4/22
おわり！

[次(Part5/22)へ](https://qiita.com/rudorufu1981/items/2683c3988b246c9cf9ce)