水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Regular Contest 100 : D - Equal Cut

  • 問題

D - Equal Cut

長さ N の整数列 A を4つの連続する部分列に分けたとき、4つの数列のそれぞれの和の最大値と最小値の差を最小化すると差はどうなるか、という問題。

 

  • 解法

4つに分けるので半分の半分だと考える。最初に半分に切るところは全通り試すとして、分けて残った2つをどう分けるかと考える。(残った2つそれぞれの和) / 2 に近くして分けられればいいと思うので std::lower_bound() を使って分けるところを(「(残った2つそれぞれの和) / 2」を超える最初の要素か、その前かの)2つ試す。あとはコーナーケースとなるケースは別に処理を書いてあげれば OK。inf が十分大きくなかったみたいで WA を連発した。600 点問題にしては解法が単純な気がした。

 

  • 解答

Submission #2828595 - AtCoder Regular Contest 100

頭が悪いコードになった(長すぎる)。

f:id:babcs2035:20180712144935p:plain

f:id:babcs2035:20180712144732p:plain