目指せ水色コーダー！！！！！！
ということで、
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】(@e869120さん)
AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。
こちらの記事の初中級者が解くべき過去問精選 100 問
をPythonで解いていきます！
@e869120さんに感謝！！！！！！
過去記事リンク
全探索：全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】
全探索：工夫して通り数を減らす全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】
全探索：ビット全探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】
全探索：順列全探索
【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
...
と考える。
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で割ればいい！
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))
こいつソートしてやろうと思ったら、すでに辞書順になってた！
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がすべて含まれていればそれが答え！！！
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つ抜粋！【競技プログラミング】
より〜
次回は、以下の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
おわり！