ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

【AtCoder版!蟻本】ABC175 B - Making Triangle【準備編】

f:id:ebisuke33:20210317160144p:plain
AtCoder版!蟻本の準備編で類題としてあげられているABC175 BをPythonで解いていきます。


atcoder.jp

AtCoder Beginner Contest 175 B - Making Triangle

問題文

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

制約

・1≤N≤100
・1≤Li≤10^9
・入力は全て整数である

解答例

n = int(input())

# 棒の長さのリスト
A = list(map(int, input().split()))
A.sort()

# 条件を満たす三角形の数
ans = 0

for i in range(n-2):
    for j in range(i,n-1):
        if A[i] == A[j]: # 長さが等しければスキップ
            continue
        for k in range(j,n):
            if A[j] == A[k]: # 長さが等しければスキップ
                continue
            if A[i]+A[j]>A[k]: # 三角形として成立しているか判定
                ans += 1

print(ans)

解説

N本の棒があるとき、そのなかから長さが異なる3本を選んで 合計何個の三角形が作れるか答える問題です。

3本の組み合わせを全通り試す全探索で答えを求めていきます。

あとで三角形が成り立つか判定しやすくするために棒の長さが格納されたリストAをソートします。

次は3本の棒を選ぶ3重ループをまわして全探索です。
1本目の棒iと2本目の棒jを選んだ時点で、長さが同じでないか判定します。

長さが違ったら3本目の棒kを選びます。
3本目の棒を選んだ時も長さが同じでないか判定しますが、相手は2本目のjです。
リストAはソートしてあるので、jとkが異なればiとも異なるといえますので、jとだけ比較すれば十分です。
三角形として成り立つには、一番長い棒が 残りの2つの棒を足し合わせた長さより短い必要があります。
この判定を最後に行って、通ればansに1を足していきます。

ループを抜けたあとにansを出力すればACをとれます。



AtCoder版!蟻本(初級編)の記事リンクページはこちら
ebisuke33.hatenablog.com