東京大学プログラミングコンテスト2011: G. プログラミングコンテストチャレンジブック

,

solution

$(a, b, c)$が三角形の$3$辺を成すためには$a \le b \le c$として$a + b \gt c$が必要十分。 とりあえず数列$a$をsortし降順とする。$a_0 \ge a_1 + a_2$なら$a_0$はどうやっても使えないので再帰的に無視してよい。愚直には$(a_0, a_1, a_2)$を三角形として採用したい。 しかしこれを提出するとWAであるため、$a_0, a_1, a_2, a_3, a_4, a_5$などが$(a_0, a_1, a_2), (a_3, a_4, a_5)$以外の分割になりうる場合があることが分かる。適当に大きめに取って全探索すればよし。$O(N \log N + k!)$。

implementation

#!/usr/bin/env python3
import itertools

def greedy(a):
    while len(a) >= 3:
        if a[-3] + a[-2] > a[-1]:
            return a.pop() + a.pop() + a.pop()
        else:
            a.pop()

def bruteforce(a):
    while len(a) >= 3 and a[-3] + a[-2] <= a[-1]:
        a.pop()
    result = 0
    for b in itertools.combinations(a[- 10 :], 6):
        for partition in itertools.combinations(range(6), 3):
            c, d = [], []
            for i in range(6):
                if i in partition:
                    c += [ b[i] ]
                else:
                    d += [ b[i] ]
            if c[0] + c[1] > c[2] and d[0] + d[1] > d[2]:
                result = max(result, sum(b))
    return result

def solve(preserved_a):
    result = 0

    # greedy
    a = list(preserved_a)
    x = greedy(a)
    y = greedy(a)
    if x is not None and y is not None:
        result = max(result, x + y)

    # bruteforce
    a = list(preserved_a)
    x = bruteforce(a)
    result = max(result, x)

    return result

n = int(input())
a = sorted([ int(input()) for _ in range(n) ])
result = solve(a)
print(result)