AtCoder ABC 175 B – Making Triangle Python解説

スポンサーリンク

Making Triangle

1,⋯,N の番号がついた N 本の棒があります。棒 i (1≤iN) の長さは Li です。
このうち、三角形を作ることのできるような長さの異なる 3 本の棒を選ぶ方法は何通りあるでしょうか。
つまり、3 つの整数 1≤i<j<kN の組であって次の 2 つの条件の両方を満たすものの個数を求めてください。
Li​,Lj​,Lk がすべて異なる
3 辺の長さが Li​,Lj​,Lk であるような三角形が存在する

AtCoder Beginner Contest 「Making Triangle」

三角形を作ることができるような長さの異なる3本の棒を選ぶ方法は何通りか調べます。条件は2つあり、棒の長さが異なること、2辺を足し合わせたものが、残りの1辺より長いことです。

for文の3重ループを使い、すべての組み合わせを調べて2つの条件を満たしている個数を求めます。

n = int(input())
l = list(map(int, input().split()))

cnt = 0

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if l[i] != l[j] and l[i] != l[k] and l[j] != l[k]:
                if l[i] + l[j] > l[k] and l[i] + l[k] > l[j] and l[k] + l[j] > l[i]:
                    cnt += 1
print(cnt)

複雑に見えますが、ループの中でやっていることは、棒の長さがそれぞれ異なっているか、また、2辺を足したものが残りの1辺より長いかを調べているだけです。2つの条件を満たしていればcnt+1をします。

n = int(input())
l = list(map(int, input().split()))

l = sorted(l)
cnt = 0

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if l[i] != l[j] and l[i] != l[k] and l[j] != l[k] and l[i] + l[j] > l[k]:
                cnt += 1
print(cnt)

最初の解答コードとほとんど変わりませんが、棒の長さを入れた配列lをソートすることで、2辺を足したものと残りの1辺の長さを調べる作業が、l[i] + l[j] > l[k]だけ調べればよいことになります。

AtCoderB問題

Posted by cheese