Tenka1 Programmer Contest 2019 D - Three Colors

解法

三角形の成立条件は、3辺すべてについて「その辺の長さが、他の2辺の長さの合計より小さい」ことです。ただこれをそのまま扱おうとすると3辺全部の長さを管理しながらDPなどをする必要があり、難しそうです。

逆に三角形が成立しない条件を考えます。それはある辺について「その辺の長さが、他の2辺の長さの合計以上である」ことです。こうするとずっと考えやすくなります。

仮に条件を満たさない辺を $R$ としましょう。3辺の長さの合計は与えられた $a_{i}$ の合計になるので、この値を $S$ と置くと $R+G+B = S$ です。辺 $R$ について三角形が成立しない条件は $R \ge G+B$ と書けるので、これは $R \ge \frac{S}{2}$ となります。これで $R$ の長さだけを管理すれば良いことが分かり、以下のようなDPで場合の数を計算することができます。

$dp\lbrack i \rbrack \lbrack j \rbrack =$ 各要素を赤緑青の3色に塗り分け、その色を $i$ 個目まで決めた時に、赤を塗った要素の合計が $j$ であるような場合の数

遷移はシンプルで、 $dp\lbrack i \rbrack \lbrack j \rbrack$ から $i+1$ 番目の要素を赤に塗ると $dp\lbrack i+1 \rbrack \lbrack j+a_{i+1} \rbrack$ に遷移し、他の2色に塗った場合は（つまり、2倍して） $dp\lbrack i+1 \rbrack \lbrack j \rbrack$ に遷移します。最終的に $j \ge \frac{S}{2}$ であるような $j$ に対して $dp\lbrack N \rbrack \lbrack j \rbrack$ を合計したものが「辺 $R$ について三角形が成立しない条件を満たすような場合の数」です。

対称性より辺 $G, B$ についても同じなので、上記の値を3倍して全事象数 $3^{N}$ から引けば終わり…かと思いきやそうはいきません。私もこれを実装した後サンプル2が合わなくて手が止まりました。複数の辺について同時に三角形が成立しない条件を満たすケースがあり、それらは重複して数えられているので戻してあげないといけません。