[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 4/22]

** Visez un codeur bleu clair! !! !! !! !! !! ** **

Alors [Directives pour améliorer AtCoder, un pro de la compétition enseigné par Red Coder [Édition intermédiaire: Visez 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 a rassemblé 100 bonnes questions éducatives qui conviennent aux codeurs marron et vert afin d'obtenir un codeur bleu clair, ou une note de 1200, avec un petit nombre de questions.

100 questions passées que les débutants et les intermédiaires devraient résoudre dans cet article` Sera résolu avec ** Python **! Merci à @ e869120! !! !! !! !! !!

Lien vers l'article précédent

** Rechercher tout: Tout lister ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part1 / 22] ** Recherche complète: toute énumération pour réduire le nombre de rues en concevant ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part2 / 22] ** Recherche complète: recherche complète de bits ** [[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Recherche complète: avant la recherche complète ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part4 / 22] ** Recherche par section ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part5 / 22] ** Recherche de priorité de profondeur ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part6 / 22] ** Recherche de priorité de largeur ** [Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part7 / 22]

** (Ajouté le 07/05/2020) **

• Supplément Entrez à partir de l'article (** Partie 6 **) dans cette série de 100 questions input()→sys.stdin.readline().rstrip() Je change pour! [Python] Competitive Pro Template [At Coder] J'ai également fait un article pour le modèle, alors veuillez l'utiliser si vous le souhaitez ~

"Partie 4" -Recherche complète séquentielle-

Nous allons résoudre les 3 questions suivantes!

Recherche complète: avant la recherche complète

15　AtCoder Beginner Contest 145 C - Average Length 16　AtCoder Beginner Contest 150 C - Count Order 17 ALDS_13_A-8 Le problème de la reine est intéressant.

15　AtCoder Beginner Contest 145 C - Average Length Difficulty:297 Vous n'avez pas du tout besoin d'utiliser Numpy, mais j'ai appris à l'utiliser, donc Un style activement utilisé.

** L'ordre est ʻitertools.permutationsVous pouvez utiliser celui-ci! ** ** (0,1,2): Ville 0 → Ville 1 → Ville 2 (0,2,1): Ville 0 → Ville 2 → Ville 1 (1,0,2)`: Ville 1 → Ville 0 → Ville 2 ... Je pense.

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

La raison pour laquelle il est inclus dans tuple est qu'une erreur se produira à moins que la clé de type de dictionnaire ne soit hachable!

• Référence (article précédent) [Python] JOI 2007 Final 3 --Les ruines les plus anciennes ((1) Le vecteur de mathématiques du lycée, (2) "dans la liste" est extrêmement lent) [Chez Coder]

np.linalg.norm(vector) Ce mec me donne une belle distance vectorielle!

Le vecteur inverse a la même distance, je vais donc le mettre dans le dictionnaire.

Une autre solution
Pour ceux qui maîtrisent les mathématiques, cette solution est également disponible! (Bien que ce ne soit plus une histoire de recherche de séquence complète ...)

Si vous pouvez trouver une solution générale de N = n (en utilisant un cahier et un stylo), la quantité de calcul sera considérablement réduite! !! !! De la solution générale de «N = n» La réponse est de doubler la somme des distances entre deux points différents et de diviser par «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)) Quand j'ai pensé à trier ce type, c'était déjà dans l'ordre lexical!

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

** Je n'ai pas pu le résoudre! Ou y a-t-il quelqu'un qui puisse résoudre ce problème à première vue? ?? ?? ** ** Mais c'était un problème intéressant ~ Si vous google, cela semble être un problème célèbre nommé N Queen Problem!

Pensez comme suit!

1. ʻitertools.permutations (range (8)) ʻet son ensemble d'index déterminent de manière unique les huit emplacements de Q! ** 8! Recherchez tous les modèles! !! !! ** ** D'ailleurs, à ce stade, les ** restrictions verticales et horizontales ** sont supprimées! Vérifiez les ** contraintes diagonales ** pour chaque motif en 2.1! C'est impossible si vous ne le savez pas w (Voir le code AC ci-dessous pour plus de détails w) Si x + y et x-y sont usés, ils sont sur la diagonale, donc NG! !! !! Souvenons-nous! Cette idée est intéressante! Si tous les Q donnés sont inclus dans celui qui a effacé la ** contrainte diagonale ** de 3.2, c'est la réponse! !! !!

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

J'essaye de ne pas approfondir le nid en mettant «continuer» au moment où il n'est plus possible de répondre. Plus le nid est profond, plus il est difficile de comprendre le code! Articles précédents [[Code lisible] 5 extraits![Programmation du concours]] (https://qiita.com/rudorufu1981/items/81f305b4686ab8cc5120) Que ~

La prochaine fois, je résoudrai les 6 questions suivantes!

Recherche de bisection

18 ALDS_4_B --Dichotomie C'est un problème de base. Vous pouvez également le résoudre avec une carte, mais essayez de le résoudre avec une dichotomie. 19 JOI 2009 Finale 2 - Pizza 20 Concours AtCoder Débutant 077 C - Festival Snuke Intéressant. 21 Concours pour débutants AtCoder 023 D - Le roi du tir est bon sur le plan éducatif. 22 AtCoder Regular Contest 054 B - La loi de Moore Elle peut être résolue en différenciant et en dichotomisant. Puisque l'histoire est liée à la recherche de trois minutes, je pense qu'il est bon de vérifier cela également. 23 JOI 2008 Final 3 - Fléchettes C'est un problème que vous pouvez concevoir et rechercher en deux.

Part4/22 fin!

Suivant (Partie 5/22)