2021/11/10
B - Making Triangleをpythonで解く
問題
問題のリンク https://atcoder.jp/contests/abc175/tasks/abc175_b
N本の棒が与えられるので、辺の長さが異なる三角形を作ることが出来る組み合わせが何通りであるか調べるというもの。
解き方
三角形になるための条件は
2つの辺の長さを足し合わせると残りの1つの辺の長さより長くなる。
また、2の辺の長さを引いた時、残りの1つの辺の長さより短くなる。
とのこと。
加えて長さが全て異なる状態でないといけないので、
棒A、B、Cが
A < B < C の場合に A + B > C
である時に三角形が作れると言えそう。
棒A、B、Cを選び、A < B < C かつ A + B > Cの場合にカウントアップする。
あらかじめソートしておけばA < B < Cであるかは見なくてもよい。
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for a in range(N):
for b in range(a + 1, N):
if L[a] == L[b]:
continue
for c in range(b + 1, N):
if L[a] == L[c] or L[b] == L[c]:
continue
if L[a] + L[b] > L[c]:
ans += 1
print(ans)
ACしたもの↓
https://atcoder.jp/contests/abc175/submissions/27165280