読者です 読者をやめる 読者になる 読者になる

Educational Codeforces Round 21 D: Array Division

f:id:parukii:20170517024850j:plain

n=1のとき明らかにNO
よってn>=2とする。
とりあえず、挿入は考えずに配列を前の部分(S)と後の部分(T)に分けてみる。ただし、S,Tは空であってもよいとする。
z=Σ[x∈S](x), w=Σ[y∈T](y)とする。
場合1. z=wの場合
ある要素を選んで同じ場所に挿入すればいいからYES
場合2. z>wの場合

Sから値vを取り除いてTに挿入したときに和が等しくなればYES
すなわち
z-v = w+vより
v = (z-w)/2としてv∈SならばYES
場合3. w>zの場合
場合2.と同様

S,Tはすべて試す。つまり、全ての前の部分の長さ(後ろの部分の長さ)を総当りで固定して、上記のチェックをすればいい。