Pythonで理解する蟻本「1-6 三角形」(p.21)
この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「1-6 三角形」(p.21)
のコードをPythonで書き直したものとなっています。
入力
入力例
22ページに書かれているように、この問題はで解くことができます。 まず、 で解く解法について説明します。 n = 5 を入力例として考えてみましょう。 まず、aを昇順にソートしてみます。 n = 5 少し考えやすくなりました。(以下aは昇順に並んでいるものとして考えます) ここで、周長が最大となる三角形の辺をとおくと となることが分かります。以下、証明を載せておきます。 【証明】 周長が最大となる三角形の辺をとおいたとき、となることを示す。 周長が最大となる三角形を三角形Pとし、その三辺を…① とおいたとき、…② となる三角形が存在すると仮定する。 このとき①, ②より、…③ となる。 よって③よりとなる。 また、①より三角形の成立条件から …④ となる。 ここで、を三辺とする三角形の存在について考えると ①より ・ ・ となる。 また、④より となりを三辺とする三角形が存在することが分かる。この三角形をQとおく。 このとき、三角形Pの周長をPL, 三角形Qの周長をQLとおくと このときから となる。 このことは三角形Pの周長が最大であることに反する。よって矛盾。 よって、周長が最大となる三角形の辺をとおいたとき、となる。■ 周長が最大となる三角形の辺をとおくととなることが分かったので と定義される数列を考えると、この問題は ・ ・ となるについての最大値を求めよ。(ただし条件を満たすが存在しない際には0を答えとする。) という問題に言い換えることができます。 このとき、各について条件を満たすは二分探索によってで調べることができます。 よって全体の計算量はとなり、全探索で解く場合よりも大幅に計算量を減らすことができます。
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)
別解
解法
a = [3, 4, 2, 10, 5]
a = [2, 3, 4, 5, 10]
別解のコード
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)