クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「1-6 三角形」(p.21)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「1-6 三角形」(p.21)
のコードをPythonで書き直したものとなっています。

入力

n\\a_1\,…\,a_n

入力例



5
2 3 4 5 10

解答

# 入力
n = int(input())
a = list(map(int,input().split()))

ans = 0 # 答え

# 棒を重複して選ばないようi < j < kとなるようにしている
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            LEN = a[i] + a[j] + a[k]        # 周長
            ma = max(a[i], max(a[j], a[k])) # 最も長い棒の長さ
            rest = LEN - ma                 # 他の2本の棒の長さの和
            
            if ma < rest:
                # 三角形が作れるので、答えを更新できれば更新
                ans = max(ans, LEN)

# 出力
print(ans)

別解

22ページに書かれているように、この問題はO({n}\,log\,{n})で解くことができます。

まず、 O({n}\,log\,{n})で解く解法について説明します。

解法

n = 5
a = [3, 4, 2, 10, 5]

を入力例として考えてみましょう。


まず、aを昇順にソートしてみます。(O({n}\,log\,{n}))

n = 5
a = [2, 3, 4, 5, 10]

少し考えやすくなりました。(以下aは昇順に並んでいるものとして考えます)

ここで、周長が最大となる三角形の辺をa_i, a_j, a_k \left(1\leq{i}<{j}<{k}\leq{n}\right) とおくと

i + 1 = j

となることが分かります。以下、証明を載せておきます。


【証明】

周長が最大となる三角形の辺をa_i,a_j,a_k\,(1\leq{i}<{j}<{k}\leq{n})とおいたとき、i + 1 = jとなることを示す。

周長が最大となる三角形を三角形Pとし、その三辺をa_i,a_j,a_k\,(1\leq{i}<{j}<{k}\leq{n})…① とおいたとき、i + 1 \neq j…② となる三角形が存在すると仮定する。

このとき①, ②より、i + 2 < j…③ となる。

よって③よりa_i < a_(i+1) < a_jとなる。


また、①より三角形の成立条件から

a_i + a_j > a_k …④

となる。


ここで、a_{i+1},a_j,a_kを三辺とする三角形の存在について考えると

①より

a_{i+1} + a_k > a_j

a_j + a_k > a_{i+1}

となる。

また、④より

\begin{eqnarray}
a_{i+1} + a_j &>& a_i + a_j \\
&>& a_k
\end{eqnarray}

となりa_{i+1},a_j,a_kを三辺とする三角形が存在することが分かる。この三角形をQとおく。


このとき、三角形Pの周長をPL, 三角形Qの周長をQLとおくと

PL = a_i + a_j + a_k

QL = a_{i+1} + a_j + a_k


このときa_i < a_{i+1}から

\begin{eqnarray}
PL &=& a_i + a_j + a_k \\
&<& a_{i+1} + a_j + a_k \\
&=& QL
\end{eqnarray}

となる。


このことは三角形Pの周長が最大であることに反する。よって矛盾。

よって、周長が最大となる三角形の辺をa_i,a_j,a_k\,(1\leq{i}<{j}<{k}\leq{n})とおいたとき、i + 1 = jとなる。■



周長が最大となる三角形の辺をa_i,a_j,a_k (1\leq{i}<{j}<{k}\leq{n})とおくとi + 1 = jとなることが分かったので

b_i = a_i + a_{i+1} (1\leq{i}\leq{n-1})

と定義される数列bを考えると、この問題は

b_i,a_j (1\leq{i}<{i+1}<{k}\leq{n})

a_j < b_i

となるb_i,a_jについてb_i + a_jの最大値を求めよ。(ただし条件を満たすb_i,a_jが存在しない際には0を答えとする。)

という問題に言い換えることができます。


このとき、各b_iについて条件を満たすa_jは二分探索によってO({n}\,log\,{n})で調べることができます。

よって全体の計算量はO({n}\,log\,{n})となり、全探索で解く場合よりも大幅に計算量を減らすことができます。


別解のコード

from bisect import bisect_left

# 入力
n = int(input())
a = list(map(int,input().split()))

ans = 0 # 答え

# aを昇順にソートする
a.sort()

b = [a[i] + a[i+1] for i in range(n-2)]

for i in range(n - 2):
    j = bisect_left(a, b[i])
    if i + 3 <= j:
        ans = b[i] + a[j - 1]

# 出力
print(ans)