[Python] ABC133B (upper right triangle problem) [At Coder]

A place where a program beginner is likely to trip. Double loop without duplication. I arbitrarily define this type of problem as the upper right triangle problem w

ABC133B Difficulty:137 It is difficult to understand the problem if there are subscripts ... For the time being, I can't imagine it even if it's called D dimension, so I imagine it in 2 dimensions. In short ① Calculate all combinations of distances between two different points ② Whether each distance is an integer If you look up k

① Calculate all combinations of distances between two different points

If you code the full search of the upper right triangle (5 rows * 5 columns), it looks like this

test.py

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

i is the 0th line (A line), the 1st line (B line), the 2nd line (C line), the 3rd line (D line), and the 4th line (E line). When i is 0, j is range (1,5) → 1,2,3,4 When i is 1, j is range (2,5) → 2,3,4 When i is 2, j is range (3,5) → 3,4 When i is 3, j is range (4,5) → 4 When i is 4, j is range (5,5) → none, so nothing is processed. ⇨ Firmly ** You can search all 10 places (4 + 3 + 2 + 1 + 0) of the triangle (yellow part!) ** on the upper right!

If you can understand this, no matter what the upper right triangle problem comes, "I'm not afraid of anything anymore"

② Whether each distance is an integer

This is easy. %1==0 or is_integer I think it doesn't matter which one. I'm not good at English, so I use the former.

①＋② In summary, it looks like this

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)

I think that the place where temp = 0 is described will become intuitive if you manage the number of problems. The formula for the distance between two points is to remember junior high school mathematics!

Similar subject (triple loop problem without duplication of upper right triangle problem)

I think this will deepen your understanding. Number of AOJ (ITP1_7_B) combinations

Like this~

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)

It's not the main subject of this article, but if you talk about the extras, k = x-i-j (k condition: 1 <= k <= n and j <k) By setting it, you can solve it with a double for statement! !! !!

** (Added on 2020/05/07) ** Currently, the problem of the above triple for statement Write code using ʻitertools.combinations`! Click here for details! [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part1 / 22]

** (Added on May 26, 2020) **

• Supplement In the figure above

--Full search of the upper right triangle - itertools.combinations(range(N),2) --Full search of upper right triangle + shaded area - itertools.combinations_with_replacement(range(N),2)

It will be. ʻItertools.combinations_with_replacement` is a duplicate combination! !! !!

end!