[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 4/22]

** Aim for a light blue coder! !! !! !! !! !! ** **

So [Guidelines for improving AtCoder, a competition pro taught by Red Coder [Intermediate Edition: Aim for Light Blue Coder! ]]( 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 has collected 100 good educational questions that are appropriate for brown and green coders to achieve a light blue coder, or rating 1200, with a small number of questions.

100 past questions that beginners and intermediates should solve in this article` Will be solved with ** Python **! Thanks to @ e869120! !! !! !! !! !!

Past article link

** Search all: List all ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part1 / 22] ** Full search: All enumeration to reduce the number of streets by devising ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part2 / 22] ** Full search: Bit full search ** [[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Full search: Permutation full search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part4 / 22] ** Binary search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part5 / 22] ** Depth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part6 / 22] ** Breadth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]

** (Added on 2020/05/07) **

• Supplement Enter from the (** Part 6 **) article in this 100-question series input()→sys.stdin.readline().rstrip() I'm changing to! [Python] Competitive template [At Coder] I also made an article for the template, so please use it if you like ~

"Part 4" ~ Permutation full search ~

We will solve the following 3 questions!

Full search: Permutation full search

15　AtCoder Beginner Contest 145 C - Average Length 16　AtCoder Beginner Contest 150 C - Count Order 17 ALDS_13_A -8 Queens problem is interesting.

15　AtCoder Beginner Contest 145 C - Average Length Difficulty:297 You don't have to use Numpy at all, but I've learned how to use it, so A style that is actively used.

** The permutation is ʻitertools.permutationsIt's OK if you use this one! ** ** (0,1,2): Town 0 → Town 1 → Town 2 (0,2,1): Town 0 → Town 2 → Town 1 (1,0,2)`: Town 1 → Town 0 → Town 2 ... I think.

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

The reason why it is enclosed in tuple is that a dictionary type key must be hashable to cause an error!

• Reference (past article) [Python] JOI 2007 Final 3 --- Oldest Ruins ((1) High School Math Vector, (2) "in List" is extremely slow) [AtCoder]

np.linalg.norm(vector) This guy gives me a nice vector distance!

Since the reciprocal vector has the same distance, I will put it in the dictionary.

Another solution
For those who are good at math, this solution is also available! (Although it is no longer a story of permutation full search ...)

If you can find a general solution of N = n (using a notebook and a pen), the amount of calculation will be drastically reduced! !! !! From the general solution of N = n The answer is to double the sum of the distances between two different points and divide by 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)) When I thought about sorting this guy, it was already in lexicographic order!

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 Queens Problem

** I couldn't solve it! Or is there anyone who can solve this problem at first sight? ?? ?? ** ** But it was an interesting problem ~ If you google, it seems to be a famous problem named N Queens problem!

Think as follows!

1. ʻitertools.permutations (range (8)) `and its index set uniquely determine the eight locations of Q! ** 8! Search all patterns! !! !! ** ** By the way, at this point, ** vertical and horizontal restrictions ** are cleared! Check ** diagonal constraints ** for each pattern in 2.1! It is impossible if you do not know this w (See the AC code below for details w) If x + y and x-y are worn, they are on the diagonal line, so NG! !! !! Let's remember! This idea is interesting! If all the given Qs are included in the one that cleared the ** diagonal constraint ** of 3.2, that is the answer! !! !!

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='')

By setting continue at the moment when it is no longer possible to answer, we try not to deepen the nesting. The deeper the nest, the harder it is to understand the code! Past articles [[Readable Code] 5 excerpts![Competitive programming]] (https://qiita.com/rudorufu1981/items/81f305b4686ab8cc5120) Than~

Next time, I will solve the following 6 questions!

Binary search

18 ALDS_4_B --Binary search This is a basic problem. You can solve it with map, but try solving it with a binary search. 19 JOI 2009 Final 2 --Pizza 20 AtCoder Beginner Contest 077 C --Snuke Festival Interesting. 21 AtCoder Beginner Contest 023 D --Shooting King Educationally good. 22 AtCoder Regular Contest 054 B --Moore's Law It can be solved by differentiating and dichotomizing. The story is connected to the ternary search, so I think you should check that as well. 23 JOI 2008 Final Round 3-Darts This is a challenge problem that you can devise and search for in two.

Part4/22 end!

Next (Part 5/22)