[Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil 4/22]

** Streben Sie einen hellblauen Codierer an! !! !! !! !! !! ** ** **

Damit [Richtlinien zur Verbesserung von AtCoder, einem von Red Coder gelehrten Wettbewerbsprofi [Zwischenausgabe: Ziel für hellblauen 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 hat 100 gute pädagogische Fragen gesammelt, die für braune und grüne Codierer geeignet sind, um mit einer kleinen Anzahl von Fragen einen hellblauen Codierer oder eine Bewertung von 1200 zu erzielen.

"100 frühere Fragen, die Anfänger und Fortgeschrittene in diesem Artikel lösen sollten" Wird mit ** Python ** gelöst! Vielen Dank an @ e869120! !! !! !! !! !!

Link zum letzten Artikel

** Alle durchsuchen: Alle auflisten ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil 1/22] ** Vollständige Suche: Alle Aufzählungen zur Reduzierung der Anzahl der Straßen durch Ausarbeitung ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part2 / 22] ** Vollständige Suche: Bit vollständige Suche ** [[Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Vollständige Suche: Vollständige Suche weiterleiten ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part4 / 22] ** Halbierungssuche ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part5 / 22] ** Suche nach Tiefenpriorität ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part6 / 22] ** Suche nach Breitenpriorität ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part7 / 22]

** (Hinzugefügt am 2020/05/07) **

• Ergänzung Geben Sie aus dem Artikel (** Teil 6 **) in dieser Serie mit 100 Fragen ein input()→sys.stdin.readline().rstrip() Ich wechsle zu! [Python] Competitive Pro-Vorlage [At Coder] Ich habe auch einen Artikel für die Vorlage erstellt. Bitte verwenden Sie ihn, wenn Sie ~ mögen

"Teil 4" -Sequentielle vollständige Suche-

Wir werden die folgenden 3 Fragen lösen!

Vollständige Suche: Vollständige Suche weiterleiten

15　AtCoder Beginner Contest 145 C - Average Length 16　AtCoder Beginner Contest 150 C - Count Order 17 ALDS_13_A-8 Queen Problem ist interessant.

15　AtCoder Beginner Contest 145 C - Average Length Difficulty:297 Sie müssen Numpy überhaupt nicht verwenden, aber ich habe gelernt, wie man es verwendet Ein Stil, der aktiv genutzt wird.

** Die Reihenfolge ist itertools.permutations. Sie können diese verwenden! ** ** ** (0,1,2): Stadt 0 → Stadt 1 → Stadt 2 (0,2,1): Stadt 0 → Stadt 2 → Stadt 1 (1,0,2): Stadt 1 → Stadt 0 → Stadt 2 ... Ich denke.

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

Der Grund, warum es in "Tupel" eingeschlossen ist, ist, dass ein Fehler auftritt, es sei denn, der Schlüssel für den Wörterbuchtyp ist "Hashable"!

• Referenz (früherer Artikel) [Python] JOI 2007 Final 3 - Die ältesten Ruinen ((1) Mathematikvektor der High School, (2) "in Liste" ist extrem langsam) [At Coder]

np.linalg.norm(vector) Dieser Typ gibt mir eine schöne Vektorentfernung!

Der inverse Vektor hat den gleichen Abstand, daher werde ich ihn in das Wörterbuch aufnehmen.

Eine andere Lösung
Für diejenigen, die gut in Mathematik sind, ist diese Lösung auch verfügbar! (Obwohl es sich nicht mehr um eine vollständige Sequenzsuche handelt ...)

Wenn Sie eine allgemeine Lösung von N = n finden (mit einem Notizbuch und einem Stift), wird der Rechenaufwand drastisch reduziert! !! !! Aus der allgemeinen Lösung von "N = n" Die Antwort ist, die Summe der Abstände zwischen zwei verschiedenen Punkten zu verdoppeln und durch N zu dividieren!

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)) Als ich darüber nachdachte, diesen Kerl zu sortieren, war er bereits in lexikalischer Reihenfolge!

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

** Ich konnte es nicht lösen! Oder gibt es jemanden, der dieses Problem auf den ersten Blick lösen kann? ?? ?? ** ** ** Aber es war ein interessantes Problem ~ Wenn Sie googeln, scheint es ein berühmtes Problem namens N Queen Problem zu sein!

Denken Sie wie folgt!

1. itertools.permutations (range (8)) und sein Indexsatz bestimmen eindeutig die acht Positionen von Q! ** 8! Suche alle Muster! !! !! ** ** ** Übrigens sind an dieser Stelle die ** vertikalen und horizontalen Einschränkungen ** aufgehoben! Überprüfen Sie ** diagonale Einschränkungen ** für jedes Muster in 2.1! Es ist unmöglich, wenn Sie dies nicht wissen. W (Einzelheiten finden Sie im AC-Code unten. W) Wenn x + y und x-y getragen werden, befinden sie sich auf der diagonalen Linie, also NG! !! !! Lass uns erinnern! Diese Idee ist interessant! Wenn alle gegebenen Qs in dem enthalten sind, der die ** diagonale Beschränkung ** von 3.2 aufgehoben hat, ist das die Antwort! !! !!

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

Ich versuche, das Nest nicht zu vertiefen, indem ich "Weiter" in dem Moment setze, in dem es nicht mehr möglich ist zu antworten. Je tiefer das Nest, desto schwieriger ist es, den Code zu verstehen! Frühere Artikel [[Lesbarer Code] 5 Auszüge![Wettbewerbsprogrammierung]] (https://qiita.com/rudorufu1981/items/81f305b4686ab8cc5120) Als ~

Nächstes Mal werde ich die folgenden 6 Fragen lösen!

Halbierungssuche

18 ALDS_4_B - Dichotomie Dies ist ein Grundproblem. Sie können es auch mit einer Karte lösen, aber versuchen Sie es mit einer Dichotomie. 19 JOI 2009 Finale 2 - Pizza 20 AtCoder Anfängerwettbewerb 077 C --Snuke Festival Es ist interessant. 21 AtCoder Anfängerwettbewerb 023 D - Shooting King Pädagogisch gut. 22 AtCoder Regular Contest 054 B - Moores Gesetz Es kann durch Differenzieren und Dichotomisieren gelöst werden. Da die Geschichte mit der dreiminütigen Suche verbunden ist, halte ich es auch für gut, dies zu überprüfen. 23 JOI 2008 Final 3 --Darts Dies ist ein Herausforderungsproblem, das Sie in zwei Hälften entwickeln und suchen können.

Part4/22 Ende!

Weiter (Teil 5/22)