zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC138-C「Alchemist」です。
ポイント
サンプルを見ても，直感的に「小さいペア同士の平均を取っていけば良さそう」というのは察することができそうです。本記事では，$N=3$のとき「小さいペア同士の平均を取っていけば良い」ことの証明を行います。すると，数学的帰納法を利用すればうまいこと一般の$N$に対しても証明を行うことができそうです。
おさえるべき内容
サンプルから直感的な操作を察する
証明
$x\leq y \leq z$なる$3$つの正の整数を考えます。このとき，以下の3つの値の大小関係を比較します。
\begin{align}
a &= \frac{\frac{x+y}{2} + z}{2} \\
b &= \frac{\frac{x+z}{2} + y}{2} \\
c &= \frac{\frac{y+z}{2} + x}{2} \\
\end{align}
a &= \frac{\frac{x+y}{2} + z}{2} \\
b &= \frac{\frac{x+z}{2} + y}{2} \\
c &= \frac{\frac{y+z}{2} + x}{2} \\
\end{align}
サンプルから察した直感としては$a \geq b \geq c$となりそうです。実際に計算してみましょう。計算過程は省略します。
\begin{align}
a - b &= \frac{1}{4}(z-y) \geq 0 \\
a - c &= \frac{1}{4}(z-x) \geq 0 \\
b - c &= \frac{1}{4}(y-x) \geq 0 \\
\end{align}
a - b &= \frac{1}{4}(z-y) \geq 0 \\
a - c &= \frac{1}{4}(z-x) \geq 0 \\
b - c &= \frac{1}{4}(y-x) \geq 0 \\
\end{align}
したがって，$a \geq b \geq c$が示せました。数学的帰納法を利用すれば，一般の$N$に対しても同様の主張を示すことができるでしょう。以上より，実装は受け取った入力を小さい順にソートして前から平均を取っていけばOKです。
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
int main(){
int N;
cin >> N;
int V[N];
rep(i, N){
cin >> V[i];
}
sort(V, V+N);
// 初期値として最初の2つの要素平均を取る
double ans = (V[0]+V[1]) / 2.0;
// 次の要素との平均を取るという操作を繰り返す
rep(i, N-2){
ans = (ans + V[i+2]) / 2.0;
}
cout << ans << endl;
}
コメント