Pythonで三角形の最大周囲長を求めるアルゴリズムと実装方法

問題の概要

正の整数の長さが格納された配列Aが与えられたとき、その中から3つの長さを選んで作れる「面積が0より大きい三角形」のうち、周囲の長さ（perimeter）が最大になるものを求めます。もし面積が0より大きい三角形を一つも作れない場合は、0を返します。

例えば、入力が [3,6,2,3] の場合、出力は 8 となります。これは、長さ3、3、6の3辺を選ぶと、3 + 3 + 6 = 12ではなく、実際には条件を満たす組み合わせの中で最大の周囲長が8になるためです。

解法のアプローチ

この問題は、次の手順で効率的に解くことができます。

• 配列Aを昇順にソートする
• 末尾（最も大きい値）から要素を3つ取り出し、それぞれ a、b、c とする（a ≥ b ≥ c）
• 三角形の成立条件である「b + c > a」を満たすか確認する
• 満たさない場合、a、b、c を1つずつずらして（スライドさせて）再度チェックする
• 配列が空になり条件を満たす組み合わせが見つからなければ、0を返す

なぜこの方法が有効か

ソート済みの配列では、最大の3つの値から順に試していくのが最適です。三角形の成立条件（2辺の和が残りの1辺より大きい）を満たさない場合、それより小さい値との組み合わせでも同じ問題が起こるため、候補を1つずつずらしながら調べることで、無駄なく答えにたどり着けます。計算量はソートに伴い O(n log n) となります。

Pythonでの実装例

以下のコードで、実際の動作を確認してみましょう。

class Solution:
    def largestPerimeter(self, A):
        A.sort()
        a, b, c = A.pop(), A.pop(), A.pop()
        while b + c <= a:
            if not A:
                return 0
            a, b, c = b, c, A.pop()
    return a + b + c

ob = Solution()
print(ob.largestPerimeter([3, 6, 2, 3]))

入力

[3, 6, 2, 3]

出力

8

コードの解説

まず A.sort() で配列を昇順に並べ替えます。A.pop() を3回呼び出すことで、最も大きい値から順に a、b、c に代入します。whileループ内では、三角形の成立条件「b + c > a」を満たしているかを判定し、満たしていなければ候補を1つずつずらします。配列が空になった時点で条件を満たす組み合わせが存在しないため、0を返します。条件を満たした瞬間に a + b + c を返すことで、最大の周囲長が得られます。

このように、ソートと貪欲法（greedy approach）を組み合わせることで、シンプルかつ効率的に三角形の最大周囲長を求めることができます。