Tenka1 Programmer Contest 2019 D. Three Colors

問題

N個の整数aiが与えられる。
この整数に赤、緑、青のいずれかの色を塗る。
このとき、以下の条件を満たすような塗りかたの通り数を998244353で割ったあまりを求めよ。
「それぞれの色で塗った整数の和をR,G,Bとするとき、三辺の長さがそれぞれR,G,Bであるような正の面積の三角形が存在する」

制約

• 3 <= N <= 300
• 1 <= ai <= 300

解法

三角形が正の面積を持つ条件は、「三辺のどれか一辺が他の二辺の和より長い」と言える。
三辺の和は整数の全部の和で得られるので、和をSとすると、「すべての辺は長さ1以上で、一番長い辺の長さ < S/2」であればよい。

これを直接求める代わりに、余事象・包除原理っぽく考える。
求めたい通り数は、
(全塗りかた) - ( R>=S/2 ) - ( G>=S/2 ) - ( B>=S/2 ) + (R>=S/2かつG>=S/2) + (R>=S/2かつB>=S/2) + (G>=S/2かつB>=S/2) - (R>=S/2かつG>=S/2かつB>=S/2)
で求められる。

塗りかたは3色のいずれかなので、全塗りかたは3^N。
対称性からGとBの計算はRと同じなので、「R>=S/2」と「(R>=S/2かつB>=S/2)」はそれぞれ求めたものを3倍にすればよい。
「R>=S/2かつG>=S/2かつB>=S/2」はそのようなのは作れないので0通り。

「R>=S/2」は、dp[i][j]:=i番目までで赤に塗った整数の合計がjとなるような通り数、を求めて、dp[N][S/2以上]の合計を求めればよい。
(更新式は、GまたはBを選んだ場合「dp[i+1][j]+=2*dp[i][j]」、Rを選んだ場合「dp[i+1][j+v[i]]+=dp[i][j]」で遷移すればよい)

「(R>=S/2かつB>=S/2)」は、それぞれが等号の場合しか成り立たないので、Sが2で割り切れるときのみ考慮する。
これもdp[N][S/2]の通り数で求められる。