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

ということで、
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】(@e869120さん)

AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。

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

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

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

#「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
Difficulty:297
Numpy使わなくても全然いいけど、せっかく使い方覚えてきたので、
積極的に使っていくスタイル。

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

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】

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

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

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

N=nの一般解を(ノートとペンを使って)頑張って見つけることができれば、計算量は激減！！！

N=nの一般解より、
答えは、異なる2点間の距離の和を2倍してNで割ればいい！

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
Difficulty:338
itertools.permutations(range(1,N+1))
こいつソートしてやろうと思ったら、すでに辞書順になってた！

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 クイーン問題
解けませんでした！
というかこの問題、初見で解ける人いるの？？？
でも面白い問題でした〜
ググったら、Nクイーン問題という名前がついている有名な問題らしいです！

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

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)へ