AtCoder ABC138 C - Alchemist のわかりやすい解説

atcoder.jp

解説PDFわかりにくすぎてタイトルに「わかりやすい解説」って書いちゃった

問題概要

$N$ 項の数列 $ \{ v_1, v_2, v_3, \cdots , v_N \} $ がある。ここから2つの数字 $v_a, v_b$ を取り出して、その平均 $ \frac{v_a+v_b}{2} $ を戻す。

この操作を $N-1$ 回行うと数列の中身は1つになる。適切に操作を行って最後に残った数字を最大にしたとき、その最大値を求めよ

例

入力例2について

• 初期数列 $\{500, 300, 200\}$
• $300, 200$ を取り出して $(300+200)/2 = 250$ を戻す
• $\{500, 250\}$ となる
• $500, 250$ を取り出して $(500+250)/2 = 375$ を戻す
• $\{375\}$ となる

このように操作して最後に $375$ が残るのが最適。

解法

数列の総和を、その数列の得点として考える。最終段階での数列の得点が最大になるようにすればいい。

1回の操作で数列の得点がどのように変化するかを考える。

取り出す数字を $y, z$ とし、操作前の得点 $P_{before}$ 、操作後の得点 $P_{after}$ を考えると

\begin{align} P_{after} &= P_{before} - (y + z) + \frac{y+z}{2} \cr &= P_{before} - \frac{y+z}{2} \end{align}

よって、毎回の操作で数列の得点は減少していく。その減少幅を最小にすれば良い。

つまり、取り出す数字 $y, z$ は数列のうち最小の2つを取れば良い。

数列を $ \{ v_1, v_2, \cdots ,x, y, z \} $ のように降順ソート済みとする（ $v_1 \ge v_2 \ge v_3 \cdots x\ge y\ge z$ ）。

ここで最後尾の $y,z$ を取り出してから、$(y+z)/2$ を最後尾に戻すと数列は

$$\{ v_1, v_2, \cdots ,x, \frac{y+z}{2} \} $$

となる。ここで $$x \ge y \ge \frac{y+z}{2} \ge z$$ であるから、新しくできた数列も降順ソート済みとなっている。

この操作を繰り返し、最後に初項に残った数字が求める答えである。

実装

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N;
  cin>>N;
  vector<double> v(N);
  for(int i=0; i<N; i++){
    cin>>v[i];
  }

  sort(v.begin(), v.end(), greater<double>());

  while(v.size()>1){
    double y = v.back();
    v.pop_back();
    double z = v.back();
    v.pop_back();

    v.push_back((y+z)/2);
  }

  cout<<v.front()<<endl;
}

追記

Alchemist [AtCoder Beginner Contest 138 C] - はまやんはまやんはまやん を見て気づいたが、配列から「実際に取り出す」必要はなかった。昇順ソートで良いから、先頭からv[i+1] = (v[i]+v[i+1])/2としていけばよいのか。

ポイント

降順ソート

std::sortはデフォルトでは昇順でソートする。これを降順にするには

• 関数オブジェクトを使う greater - cpprefjp C++日本語リファレンス

vector<int> v;
...
sort(v.begin(), v.end(), greater<int>());

• ラムダ式を使う

vector<int> v;
...
sort(v.begin(), v.end(), [](int a, int b){
  return a > b;
});

関数オブジェクトを自作するという方法もあるそうだがちょっとわからんかったので省略。

おしまい

ラムダ式でソート順を操作するというところをメモしたかった。おしまい。

参考

• std::sort - cppreference.com