0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/22】

Last updated at Posted at 2020-05-02

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

ということで、
レッドコーダーが教える、競プロ・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の一般解を(ノートとペンを使って)頑張って見つけることができれば、計算量は激減!!!
IMG_2736.JPG
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)へ

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?