https://emtubasa.hateblo.jp/entry/2019/04/29/225330

解法

まず、三角形の成立条件を思い出すと、長さ $x,y,z$ の三角形が存在するには、
$x+y \gt z, y+z \gt x, z+ x\gt y$
が全て成立している必要があります。
逆に、 $x$ が最長の辺かつ $x \geqq y+z$ を満たしているとき、三角形を作成することはできません。両辺に $x$ を追加した後に2で割ると、

$x \geqq \frac{x+y+z}{2}$

という条件がでてきます。
仮にこの状況になった場合、 $x$ は $x,y,z$ の中で最も大きい値になっているはずです。
$x+y+z$ は $\sum a_{i}$ で求めることができるので、 $x \geqq \frac{x+y+z}{2}$ となるような塗り分け方は、どうにかして求めることができそうな気がします。ということで包除原理を利用して、全ての塗り分け方から、三角形を作成できないようなパターンを引くことで答えを求めることにします。
$x$ が最大であると仮定して、そのときに $x \geqq \frac{x+y+z}{2}$ となる場合の数を求めることにします。すると、これは $y,z$ が最大の場合も全く同じ状況になるので、3倍すればよいはずです。
場合の数を、動的計画法で求めていきます。

$dp[i][j] = i$ 番目までの数を割り振って、 $x$ の値が $j$ になるようなものの場合の数

とします。これは、

$dp[i+1][j] = dp[i][j] \times 2 + dp[i][j-a_{i}]$

という遷移で数え上げることができます。
右辺の1つ目の項は、 $a_{i}$ を $x$ に割り振らない場合で、残った $y,z$ のどちらかに割り振ることになるので、2倍します。 2つ目の項は $a_{i}$ を $x$ に割り振る場合です。
この遷移を利用して数え上げを行い、あとは $sum = \sum a_{i}$ として、
$\displaystyle \sum_{i=(sum+1)/2}^{sum} dp[n][i] \times 3$
を求めれば、三角形にならないパターンを数え上げることができる…
はずですが、コーナーケースが存在します。
$sum$ が偶数の場合、 $(x,y,z) = (sum/2,sum/2,0)$ となるケースが存在するかもしれません。このパターンは、上のDPをそのまま用いると重複して数えてしまいます。2つの $sum/2$ を区別して $sumA,sumB$ とすると、
$dp[n][sum/2]$ には、
$(sumA,sumB,0),(sumA,0,sumB),(sumB,sumA,0),(sumB,0,sumA)$
の4つのパターンが含まれているはずですが、最後に全体から引く際に、 $x$ が最大という条件を外してこれを3倍するため、合計12パターンが引かれることになります。が、 $(sumA,sumB,0)$ というパターンは、 $3! = 6$ 通りの並べ方しかないため、2回分引いてしまっていることになります。　
これを解消するために、これらのパターンも数え上げてしまいます。これまた動的計画法を利用します。
このパターンは、 $2$ 種類のみに $a_{i}$ を割り振ると出来上がるので、

$dp2[i][j] = i$ 番目までの数字を $x$ と $y$ のみに割り振って、 $x = j$ となるようなものの場合の数

とすると、遷移は先ほどとほぼ同じで、

$dp2[i+1][j] = dp2[i][j] + dp2[i][j-a_{i}]$

という遷移で数え上げることができます。
先ほどの2倍をする部分だけが消えた形になります。
ということで、この遷移を行うと $dp2[n][sum/2]$ は、 $(sumA,sumB,0),(sumB,sumA,0)$ の2パターン分だけ綺麗に数え上げられているはずです。
あとは、この部分の調整も行いつつ、

$sum$ が奇数の場合
$3^{N} - \displaystyle \sum_{i=(sum+1)/2}^{sum} dp[n][i] \times 3$
$sum$ が偶数の場合
$3^{N} - \displaystyle \sum_{i=(sum+1)/2}^{sum} dp[n][i] \times 3 + dp2[n][sum/2] \times 3$

を求めると、答えになります。

感想

解けるべき問題だった…？気がします。コンテスト中、似たようなDPをすることまでは思いついていたのですが、細かいところを詰められなかったのと、そもそもコーナーケースに気づいていませんでした。
雰囲気でDPを解いているのがバレる回でしたね。