https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_d

問題

$N$ 個の整数 $(a_0, \ldots, a_{N-1})$ が与えられる。与えられたすべての整数に対して、赤・緑・青のいずれかで塗り、赤・緑・青で塗られた整数の総和をそれぞれ $R, G, B$ とする。

$R, G ,B$ を3辺とする（正の面積を持つ）三角形ができるような場合の数は？

[制約]

• $3\leq N \leq 300$
• $1\leq a_i \leq 300$

愚直

まず以下の愚直なDPができる

• $\mathrm{dp}[i][r][g][b]$: A[0..i] で赤・緑・青の総和がそれぞれ $r, g, b$ となるような場合の数とするようなDP
  • もちろんTLE

$r + g + b$ は $i$ が決まれば固定で、$\sum A[0..i]$ で求まる。つまり、DP の状態を1変数減らせる。

• $\mathrm{dp}[i][r][g]$: A[0..i] で赤・緑の総和がそれぞれ $r, g$ となるような場合の数とするようなDP
  • これでもTLE

ここから先どうしても詰まってしまう。

考え方1: 図を書く

三角形の塗られている部分の総和が答え。余事象を使って、塗られていない部分を考える。