[Python] ABC133B (Problem mit dem oberen rechten Dreieck) [At Coder]

Ein Ort, an dem Programmanfänger wahrscheinlich stolpern. Doppelschleife ohne Duplizierung. Ich definiere diese Art von Problem willkürlich als das "Problem des oberen rechten Dreiecks" w

ABC133B Difficulty:137 Es ist schwierig, das Problem zu verstehen, wenn es einen Index gibt ... Im Moment kann ich es mir nicht vorstellen, auch wenn es D-Dimension heißt, also stelle ich es mir in 2 Dimensionen vor. Zusamenfassend ① Berechnen Sie alle Kombinationen von Abständen zwischen zwei verschiedenen Punkten ② Ob jede Entfernung eine ganze Zahl ist Wenn Sie nachschlagen k

① Berechnen Sie alle Kombinationen von Abständen zwischen zwei verschiedenen Punkten

Wenn Sie die vollständige Suche des oberen rechten Dreiecks (5 Zeilen * 5 Spalten) codieren, sieht es so aus

test.py

for i in range(5):
    for j in range(i+1,5):
        #Entfernungsberechnung

i ist die 0. Zeile (A-Zeile), 1. Zeile (B-Zeile), 2. Zeile (C-Zeile), 3. Zeile (D-Zeile), 4. Zeile (E-Zeile) Wenn i 0 ist, ist j "Bereich (1,5)" → "1,2,3,4" Wenn i 1 ist, ist j "Bereich (2,5)" → "2,3,4" Wenn i 2 ist, ist j "Bereich (3,5)" → "3,4" Wenn i 3 ist, ist j "Bereich (4,5)" → "4" Wenn i 4 ist, ist j "Bereich (5,5)" → keine, also wird nichts verarbeitet. ⇨ Fest ** 10 Stellen (4 + 3 + 2 + 1 + 0) im oberen rechten Dreieck (gelber Teil!) ** können vollständig durchsucht werden!

Wenn Sie das verstehen können, egal was das Problem mit dem oberen rechten Dreieck ist: "Ich habe vor nichts mehr Angst."

② Ob jede Entfernung eine ganze Zahl ist

Das ist einfach. %1==0 or is_integer Ich denke es ist egal welches. Ich kann nicht gut Englisch, also benutze ich das erstere.

①＋② Zusammenfassend sieht es so aus

test.py

def LI(): return list(map(int,input().split()))
N,D = LI()
X = [LI() for _ in range(N)]
_ans = 0
for i in range(N):
    for j in range(i+1,N):
        temp = 0
        for k in range(D):
            temp += (X[j][k]-X[i][k])**2
        if temp**0.5%1==0:
            _ans += 1
print(_ans)

Ich denke, dass der Ort, an dem "temp = 0" beschrieben wird, intuitiv wird, wenn Sie die Anzahl der Probleme verwalten. Die Formel für den Abstand zwischen den beiden Punkten lautet: Erinnern Sie sich an die Mathematik der Mittelstufe!

Ähnliches Thema (Dreifachschleifenproblem ohne Duplizierung des oberen rechten Dreiecksproblems)

Ich denke, das wird Ihr Verständnis vertiefen. Anzahl der AOJ (ITP1_7_B) -Kombinationen

So ~

test.py

def LI(): return list(map(int,input().split()))
while 1:
    n,x = LI()
    if n==x==0:
        break
    _ans = 0
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            for k in range(j+1,n+1):
                if i+j+k==x:
                    _ans += 1
    print(_ans)

Es ist nicht das Hauptthema dieses Artikels, aber wenn Sie über die Extras sprechen, k = x-i-j (k Bedingung: 1 <= k <= n und j <k) Wenn Sie es einstellen, können Sie es mit einer doppelten for-Anweisung lösen! !! !!

** (Hinzugefügt am 2020/05/07) ** Derzeit ist das Problem des oben genannten Triple for Statement Schreiben Sie Code mit itertools.combinations! Hier klicken für Details! [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil 1/22]

** (Hinzugefügt am 26. Mai 2020) **

• Ergänzung In der Abbildung oben

• Vollständige Suche im oberen rechten Dreieck
  • itertools.combinations(range(N),2)
• Vollständige Suche des oberen rechten Dreiecks + des schattierten Bereichs
  • itertools.combinations_with_replacement(range(N),2)

Es wird sein. itertools.combinations_with_replacement ist eine doppelte Kombination! !! !!

Ende!