CodeForces #266_Div2 : C. Number of Ways
問題
大きさnの整数配列aが与えられる。
aを3つに分割したとき、分割したセグメントの和が全て等しくなるような
分割方法はいくつあるか。 という問題。
解法
全体の和 を とおく。
前提として、が3の倍数でなければ解は一つも存在しない。
配列を舐め を発見した地点から終端手前までループを回し、
が出現するたびにカウントすれば解が求まるが、この方法では
となり間に合わない。
( が出現した箇所から終端までの和は明らかに
)
逆の見方をすると、 が出現した時点でのそれまでの
の個数が
正しい分割方法の解に含まれる事が分かる。
よって配列を舐めながらと
の数をカウントし、
和がとなる度にそれまでの
の数を答えとして足していけば良い。
計算量はとなる。
