ARC100/ABC102 D - Equal Cut
復習日記
D - Equal Cut
区間を区切った時の和の差が最小になるようにする問題
区間の和については累積和を持っておくことでとある区間の和は簡単に求めることができます。
この問題の答えを求めるときのポイントは真ん中を決め打ちしてから左右をそれぞれ求めるということ。
真ん中が決まってしまえば残りの半分はできるだけ均等に分ければいいのでで位置を求めることができる。
(例えばこれを極端にバランスを悪く切ってしまうとそこの差が大きくなってしまう)
これに加えて真ん中を左から右へずらすと残りの2カ所も必ず左から右へずれる。 この性質を使うと尺取り法で効率よく切る位置を求めることができる。
ここまでわかれば後は実際にシミュレートして最小値を求めることができる。
計算量はになります。
この問題は比較的実装が楽でした。
どこか1カ所を決めれば残りがで求められるので、シミュレートできる性質がこの問題に似ている気がします。
ABC062 C - Chocolate Bar
