ABC100 : D - Patisserie ABC

問題

N 個の「綺麗さ」「おいしさ」「人気度」の３つの要素があるケーキを M 個選んで食べる（重複なしで）。この時、綺麗さの合計の絶対値 + おいしさの合計の絶対値 + 人気度の合計の絶対値の最大値を求める問題。３つの要素の値は負数にもなりうる。

解法

絶対値なので単純にソートやら DP やらはできない。答えを最大化するには、それぞれ３つの要素を + 方向か - 方向かに伸ばすのがよい（これはコンテスト中に分かった）。

最終的な値がx>0ならxは出来るだけ大きくなるようにした方が得で、最終的な値がx<0ならxは出来るだけ小さくなるようにした方が得です
— eiya@プログラミング (@eiya5498513) June 16, 2018

ここから先が思いつかず、No Sub に終わった。

ここで、３つの要素を + か - のどちらに伸ばしていくのか？という方針を全通り試す。具体的には、

x を + に、y を + に、 z を + に
x を + に、y を + に、 z を - に
x を + に、y を - に、 z を - に
x を - に、y を - に、 z を - に
x を - に、y を + に、 z を - に
x を + に、y を - に、 z を + に
x を - に、y を - に、 z を + に
x を - に、y を + に、 z を + に

の８通りをすべて試す。

ある最適な選び方をしたときの答えが
ans=|Σx|+|Σy|+|Σz|
で，その時Σx<0,Σy>=0,Σz<0だったとき，
x[i]=-x[i], z[i]=-z[i];
としておくと
ans=Σx+Σy+Σz
が答えになる．
逆に最終的な評価の符号を決めてしまえばΣx+Σy+Σzを最大化すればよくなり，これは
Σx+Σy+Σz=Σ(x+y+z)
より貪欲に選んでいける
— satanic@競プロ！ (@satanic0258) June 16, 2018