zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC159-C「Maximum Volume」です。
ポイント
数学的な考察が必要な問題でした。ただし，サンプルケースからもわかる通り，直感的には体積が最大になるのは全ての辺が等しいときです。競技プログラミングでは，解答の正当性を証明する必要がないため，サンプルケースから読み取れたことを素直に実装するだけでもOKです。本記事では，以下で簡単な説明を加えます。
サンプルケースから直感的な解答を導き出す
証明
さて，3辺の合計が$L$で体積が最大になるような直方体の体積を求める問題ですが，素直に定式化してしまうと不定方程式（式の個数より未知数の個数の方が多いような方程式）になってしまいます。そこで，何を使えば良いのかと思いを巡らせる訳です。
私たちの目的は，直方体の3辺をそれぞれ$x$，$y$，$z$とおけば，目的関数$xyz$を上からおさえる（評価する）ことです。思い出していただきたいのが，相加相乗平均の関係式です。
$a_{1}, a_{2}, \cdots, a_{n} \geq 0$ のとき
\sum_{i=1}^{n} a_{i} \geq n \sqrt[n]{\prod_{i=1}^{n} a_{i}} \label{agmean}
\end{align}
が成立する。ただし，等号成立条件は$a_{1}=a_{2}=\cdots=a_{n}$である。
相加平均は相乗平均以上ですよという不等式ですね。こいつを利用すれば，不定方程式であっても相乗（平均）の最大値を求めることができるのです。少し式(\ref{agmean})変形をしてみます。
\prod_{i=1}^{n} a_{i} \leq \left( \frac{1}{n}\sum_{i=1}^{n} a_{i} \right)^{n}
\end{align}
さて，今回の問題では$n=3$，$a_1=x$，$a_2=y$，$a_3=z$としていますので，相加相乗平均の関係式より以下のような関係式が求められます。
xyz &\leq \left\{ \frac{1}{3}(x+y+z) \right\}^{3}\\
&= \frac{1}{27}(x+y+z)^3
\end{align}
この例のように，相加相乗平均の関係式は「不定方程式だけど対称性を利用して最小値や最大値を求めたい！」という場合に利用される不等式です。
実装
#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 L;
cin >> L;
cout << fixed << setprecision(10);
cout << (double) L * L * L / 27 << endl;
}
コメント