** 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! !! !! !! !! !!
** 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) **
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 ~We will solve the following 3 questions!
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! !! !!
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)))
** 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!
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!
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!
Recommended Posts