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

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

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

Recommended Posts

[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 5/22]
[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]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Part3 / 22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 1/22]
[Python] J'ai essayé de résoudre 100 questions passées que les débutants et les intermédiaires devraient résoudre [Partie 6/22]
Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (028 --033 recherche de priorité de largeur)
Résolution avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (053 --055 Méthode de planification dynamique: Autres)
Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (024 --027 Recherche de priorité en profondeur)
Résoudre avec Python [100 anciennes questions sélectionnées que les débutants et les intermédiaires devraient résoudre] (015 --017 Recherche complète: Recherche complète en avant)
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (010 --014 Recherche complète: Recherche complète de bits)
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (001 --004 Toutes les recherches: Toutes les énumérations)
Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (056 --059 Problème de l'itinéraire le plus court: méthode Dyxtra)
Résoudre avec Python [100 questions que les débutants et les intermédiaires devraient résoudre] (034-038 Méthode de planification dynamique: Knapsack DP basic)
Résolvez avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (039 --045 Méthode de planification dynamique: variante Knapsack DP)
Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (005 --- 009 Toutes les recherches: Toutes les énumérations pour réduire le nombre de rues en concevant)
[Pour les professionnels de la compétition débutants] J'ai essayé de résoudre 40 questions AOJ "ITP I" avec python
J'ai essayé de résoudre l'édition du débutant du livre des fourmis avec python
Python que je voudrais recommander aux débutants en programmation
J'ai essayé de résoudre Soma Cube avec python
J'ai essayé de résoudre le problème avec Python Vol.1
J'ai essayé de résoudre la théorie des nombres entiers d'AOJ avec Python
J'ai essayé d'énumérer les différences entre java et python
J'ai essayé de créer une interface graphique à trois yeux côte à côte avec Python et Tkinter
Django super introduction par les débutants Python! Partie 6 J'ai essayé d'implémenter la fonction de connexion
J'ai essayé de résumer les langues que les débutants devraient désormais apprendre par but
Examen mathématique précoce de l'Université Tohoku 2020 (sciences) J'ai essayé de résoudre les grandes questions 1 à 3 avec Python
Django super introduction par les débutants Python! Partie 1 J'ai essayé d'afficher une page HTML qui ne dit que "Hello World"
J'ai essayé de toucher Python (installation)
les débutants en python ont essayé de le découvrir
Je veux résoudre APG4b avec Python (seulement 4.01 et 4.04 au chapitre 4)
[Python] Un mémo que j'ai essayé de démarrer avec asyncio
[Pandas] J'ai essayé d'analyser les données de ventes avec Python [Pour les débutants]
J'ai essayé de faire un processus d'exécution périodique avec Selenium et Python
J'ai essayé de détecter facilement les points de repère du visage avec python et dlib
[Python] J'ai essayé d'expliquer des mots difficiles à comprendre pour les débutants d'une manière facile à comprendre.
J'ai essayé de résumer la gestion des exceptions Python
J'ai essayé d'implémenter PLSA en Python
J'ai essayé d'implémenter la permutation en Python
Comment écrire hors ligne en temps réel J'ai essayé de résoudre E11 avec python
Entrée standard Python3 que j'ai essayé de résumer
Je voulais résoudre ABC160 avec Python
J'ai essayé d'utiliser PyEZ et JSNAPy. Partie 2: J'ai essayé d'utiliser PyEZ
J'ai essayé d'implémenter ADALINE en Python
J'ai essayé de laisser optuna résoudre le nombre
J'ai essayé de développer un formateur qui génère des journaux Python en JSON
Django super introduction par les débutants Python! Partie 2 J'ai essayé d'utiliser les fonctions pratiques du modèle
J'ai essayé de faire la reconnaissance de caractères manuscrits de Kana Partie 2/3 Création et apprentissage de données
Je voulais résoudre ABC159 avec Python
J'ai essayé d'implémenter PPO en Python
10 erreurs Python communes aux débutants
J'ai essayé de vérifier et d'analyser l'accélération de Python par Cython
J'ai essayé de résoudre la recherche de priorité de profondeur (DFS) d'AtCoder en Python (résultat: TLE ...)
J'ai essayé de résoudre TSP avec QAOA
[Python] J'ai essayé de calculer TF-IDF régulièrement
[Chaîne de Markov] J'ai essayé de lire des citations et des émotions négatives en Python.
J'ai essayé de toucher Python (syntaxe de base)
J'ai créé un exemple pour accéder à Salesforce en utilisant Python et Bottle
Je voulais résoudre ABC172 avec Python
J'ai refactoré "J'ai essayé de faire d'Othello AI lorsque les débutants en programmation ont étudié python"
Comment écrire en temps réel hors ligne J'ai essayé de résoudre E12 avec python