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

"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!

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! !! !! IMG_2736.JPG 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)

Recommended Posts

[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 5/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 4/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 1/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 6/22]
Solve with Python [100 past questions that beginners and intermediates should solve] (028 --033 breadth-first search)
Solve with Python [100 past questions that beginners and intermediates should solve] (053 --055 Dynamic programming: Others)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (024 --027 Depth-first search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (015 --017 Full search: Permutation full search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (010 --014 Full search: Bit full search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (001 --004 All search: All enumeration)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (056 --059 Shortest path problem: Dijkstra's algorithm)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (034-038 Dynamic programming: Knapsack DP basic)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (039 --045 Dynamic programming: Knapsack DP variant)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (005 --- 009 All search: All enumeration to reduce the number of streets by devising)
[For beginners in competition professionals] I tried to solve 40 AOJ "ITP I" questions with python
I tried to solve the ant book beginner's edition with python
Python that I would like to recommend to programming beginners
I tried to solve the soma cube with python
I tried to solve the problem with Python Vol.1
I tried to solve AOJ's number theory with Python
I tried to enumerate the differences between java and python
I tried to make GUI tic-tac-toe with Python and Tkinter
A super introduction to Django by Python beginners! Part 6 I tried to implement the login function
I tried to summarize the languages that beginners should learn from now on by purpose
Tohoku University 2020 First semester math exam (science) I tried to solve major questions 1 to 3 with Python
A super introduction to Django by Python beginners! Part 1 I tried to display an HTML page that only says "Hello World"
I tried to touch Python (installation)
python beginners tried to find out
I want to solve APG4b with Python (only 4.01 and 4.04 in Chapter 4)
[Python] A memo that I tried to get started with asyncio
[Pandas] I tried to analyze sales data with Python [For beginners]
I tried to make a periodical process with Selenium and Python
I tried to easily detect facial landmarks with python and dlib
[Python] I tried to explain words that are difficult for beginners to understand in an easy-to-understand manner.
I tried to summarize Python exception handling
I tried to implement PLSA in Python
I tried to refer to the fun rock-paper-scissors poi for beginners with Python
I tried to implement permutation in Python
How to write offline real time I tried to solve E11 with python
Python3 standard input I tried to summarize
I wanted to solve ABC160 with Python
I tried using PyEZ and JSNAPy. Part 2: I tried using PyEZ
I tried to implement ADALINE in Python
I tried to let optuna solve Sudoku
I tried to develop a Formatter that outputs Python logs in JSON
A super introduction to Django by Python beginners! Part 2 I tried using the convenient functions of the template
I tried to make Kana's handwriting recognition Part 2/3 Data creation and learning
I wanted to solve ABC159 in Python
I tried to implement PPO in Python
10 Python errors that are common to beginners
I tried to verify and analyze the acceleration of Python by Cython
I tried to solve AtCoder's depth-first search (DFS) in Python (result: TLE ...)
I tried to solve TSP with QAOA
[Python] I tried to calculate TF-IDF steadily
[Markov chain] I tried to read quotes and negative emotions into Python.
I tried to touch Python (basic syntax)
I tried to create a sample to access Salesforce using Python and Bottle
I wanted to solve ABC172 with Python
I refactored "I tried to make Othello AI when programming beginners studied python"
How to write offline real time I tried to solve E12 with python