解説AC
公式解説のメモ程度です。
の累積和を
とおくと、与えられる情報は、
という風になり、
と
の一方が分かれば、もう一方がわかる
という関係になる。 この関係をグラフ化し、と
が連結ならYes。
ここまでが公式解説の内容です。
連立方程式を順に解いていくことをイメージしました。
ただ、にたどり着ければその値を求められるのは理解できますが、たどり着けないところも何か求める手段がありそうな気がして少し腑に落ちないところがあります。
話は変わりますが、この問題は、Xが実際の値が与えられた時に
から
へのコストXの有向辺
から
へのコスト-Xの有向辺
とすれば、実際にを求めることもできそうです。
また、このように考えると、牛ゲーの特殊バージョンと考えられるような感じもします。
別解として、以下のリンクのように吐き出し法で解かれている方がおり、公式解説より私的には納得できました。