AtCoderログ：0109 - ABC 138 C

問題

問題文

あなたは鍋と $N$ 個の具材を持っています。各具材は 価値 と呼ばれる実数の値を持ち、$i$ 個目 $(1 \le i \le N)$ の具材の価値は $v_i$ です。
$2$ 個の具材を鍋に入れると、それらは消滅して新たに $1$ 個の具材が生成されます。この新たな具材の価値は元の $2$ 個の具材の価値を $x,y$ として $(x+y)/2$ であり、この具材を再び鍋に入れることもできます。
この具材の合成を $N−1$ 回行うと、最後に $1$ 個の具材が残ります。この具材の価値として考えられる最大の値を求めてください。

制約

・$2 \le N \le 50$
・$1 \le v_i \le 1000$
・入力中の値はすべて整数である。

収録されている問題セット

• AtCoder Problems Boot camp for beginners Easy 100 [#017]

回答

回答1 (AC)

価値が $x,y$ の具材を合成してできた具材の価値は $(x+y)/2$ になるので、失われた価値は $x+y-(x+y)/2 = (x+y)/2$ となります。従って、具材がたくさんある場合、価値が最小の2つの具材を合成するのが良いことがわかります。

次に、価値が $x < y < z$ である3つの具材を考えます。このとき3つの具材を合成する方法は3通りあり、(1) x,y を合成してから z を合成 → 最終的な価値は $(x+y+2z)/4、(2) x,z を合成してから y を合成 → 最終的な価値は $(x+2+z)/4、(3) y,z を合成してから x を合成 → 最終的な価値は $(2x+y+z)/4、となり、(1)の価値が最も大きいことがわかります。

以上の考察により、全ての具材の価値を昇順(小さい順)にソートし、小さい方から順に合成していけば良いことがわかります。コードは以下のようになりました。

abc138c-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;

  vector<int> v(n);
  for ( int i=0; i<n; i++ ) {
    cin >> v.at(i);
  }
  
  sort( v.begin(), v.end() );
  
  float value = v.at(0);
  for ( int i=1; i<n; i++ ) {
    value = (value+v.at(i))/2.0;
  }
  
  cout << value << endl;
}

調べたこと

AtCoder の解説 → ユーザ解説

回答1と同じ方針でした。

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0108 - ABC 142 C
• 次の記事 → AtCoderログ：0110 - ABC 218 に参加しました