水色プログラミング

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

ABC100 : D - Patisserie ABC

  • 問題

D - Patisserie ABC

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

 

  • 解法

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

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

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

  1. x を + に、y を + に、 z を + に
  2. x を + に、y を + に、 z を - に
  3. x を + に、y を - に、 z を - に
  4. x を - に、y を - に、 z を - に
  5. x を - に、y を + に、 z を - に
  6. x を + に、y を - に、 z を + に
  7. x を - に、y を - に、 z を + に
  8. x を - に、y を + に、 z を + に

の8通りをすべて試す。

3つの要素をどちらの方向に伸ばしていこうと決定したら、各ケーキごとに答えの最大化に貢献してくれる度が分かる。具体的には、+ に伸ばそうとするのであれば、負数のケーキは明らかに答えの最大化に貢献してくれる度が低い。逆も同様。

よって、各ケーキごとに3つの要素の答えの最大化に貢献してくれる度を求め、それらを足し合わせ、その足し合わせた数でケーキを降順ソートし、数が大きい方から M 個食べれば答えの候補になる。これを8通りについて同様に計算し、それらの最大値を求めればよい。O(NlogN) なので余裕で間に合う。

 

  • 解答

Submission #2689819 - AtCoder Beginner Contest 100

f:id:babcs2035:20180617123709p:plain

f:id:babcs2035:20180617123846p:plain