n本の棒があります。棒iの長さはa_iです。あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えています。最大の周長を求めなさい。ただし、三角形が作れない際には0を答えとしなさい。
プログラミングコンテストチャレンジブック P.21
この問題はこの本の2番目の問題で、解くだけなら非常に簡単です。降順に並べて前から三角形になっているかみていくだけです。Pythonで書くと、
from itertools import ifilter N = 6 edges = [ 1, 10, 4, 2, 3, 6 ] edges.sort(key = lambda x: -x) # descending def is_triangle((c, b, a)): return c < b + a print sum(next(ifilter(is_triangle, (edges[k:k+3] for k in xrange(N - 2)))))
しかし、この問題は非常に興味深いです。
ここでこれに関連して次のような問題を考えてみましょう。
棒がM本あります。それぞれの棒の長さは1からNの整数を取りうるとします。M本の棒が与えられたとき、これを降順に並べて前から3つずつ取って三角形になるか調べます。例えば、10・5・4・2とすると、10と5と4では三角形になりません。次の5と4と2は三角形になります。すなわち、2回目で三角形になります。棒の長さがランダムに与えられたとき、何回目に三角形になることが期待されるでしょうか。便宜上、三角形にならなかった場合、M-1回とします。
ここで、N=100、M=10などとするとProject Euler風の問題になります。さて、どうなるでしょうか。ちなみに、1ヶ月近く前から考えていますが、まだ解けていません。
