noshi91のメモ

データ構造のある風景

The 3rd Universal Cup Stage 15: Chengdu - F

単調増加な正実数列 x によって定義される関数 \displaystyle f ( l , r ) := \sqrt{ (r - l) \sum _ {i = l} ^ {r - 1} x _ i } は Monge であることを示せ。

てんぷらによる証明

https://x.com/tempuracpp/status/1854498278190285099

区間の平均値 \displaystyle \mathrm{Av g}(l, r) := \frac{\sum _ {i = l} ^ {r - 1} x _ i}{r - l} を定義すると、 f(l, r) = (r - l) \sqrt{\mathrm{Av g}(l, r)} である。

\begin{align} & & f(l _ 0, r _ 0) + f(l _ 1 , r _ 1) & \leq f(l _ 0 , r _ 1) + f(l _ 1, r _ 0) \cr \iff & & (r _ 0 - l _ 0) \sqrt{\mathrm{Av g}(l _ 0 , r _ 0)} + (r _ 1 - l _ 1) \sqrt{\mathrm{Av g}(l _ 1 , r _ 1)} & \leq (r _ 1 - l _ 0) \sqrt{\mathrm{Av g}(l _ 0 , r _ 1)} + (r _ 0 - l _ 1)\sqrt{\mathrm{Av g}(l _ 1 , r _ 0)} \cr \iff & & \frac{ (r _ 0 - l _ 0) \sqrt{\mathrm{Av g}(l _ 0 , r _ 0)} + (r _ 1 - l _ 1)\sqrt{\mathrm{Av g}(l _ 1 , r _ 1)} }{r _ 0 + r _ 1 - l _ 0 - l _ 1} & \leq \frac{ (r _ 1 - l _ 0) \sqrt{\mathrm{Av g}(l _ 0 , r _ 1)} + (r _ 0 - l _ 1)\sqrt{\mathrm{Av g}(l _ 1 , r _ 0)} }{r _ 0 + r _ 1 - l _ 0 - l _ 1} \end{align}

両辺とも \sqrt{} の凸結合の形であり、引数の凸結合を取ると一致する。 x の単調性から左辺のほうが偏った凸結合になっており、 \sqrt{} が凹関数であることから偏った凸結合ほど小さくなるため求める不等式を得る。 \blacksquare

証明(旧)

問題設定を連続版にする。 すなわち、 x \colon \mathbb{R} \to \mathbb{R} _ {\gt 0} を単調増加な関数として、 \displaystyle f ( l , r ) := \sqrt{ (r - l) \int _ l ^ r x(t) \mathrm d t } の Monge 性を示す。 ここから元の問題の結果も導かれることは明らか。

\displaystyle \frac{\partial ^ 2 f(l, r)}{\partial l \partial r} \leq 0 が示せれば、 \lbrack l _ 0 , l _ 1 \rbrack \times \lbrack r _ 0 , r _ 1 \rbrack において積分することで f(l _ 0 , r _ 0) - f(l _ 0 , r _ 1) - f(l _ 1 , r _ 0) + f(l _ 1 , r _ 1) \leq 0 が示され、求める不等式を得る。

まず r について偏微分すると \displaystyle \frac {\partial f(l, r)} {\partial r} = \frac{1}{2} \left( \sqrt{\frac{\int _ l ^ r x(t) \mathrm d t }{r - l} } + \sqrt{\frac{r - l}{\int _ l ^ r x(t) \mathrm d t } } x _ {r} \right) が分かる。 \displaystyle A(l, r) := \frac{\int _ l ^ r x(t) \mathrm d t }{r - l} と定義し、これを利用して l について偏微分すると \displaystyle \frac{\partial ^ 2 f(l, r)}{\partial l \partial r} = \frac{1}{4} \frac{\partial A(l, r)}{\partial l} \left( \frac{1}{\sqrt{A(l,r)} } - \frac{1}{A(l, r) \sqrt{A(l, r)} } x _ r \right) となる。 A は区間の平均値を意味しているから、 x の単調性と合わせると以下の事実が言える。

  • A(l, r) \leq x _ r
  • \displaystyle \frac{\partial A(l, r)}{\partial l} \geq 0

1 つ目の事実から、 \displaystyle \frac{1}{\sqrt{A(l,r)} } - \frac{1}{A(l, r) \sqrt{A(l, r)} } x _ r \leq 0 が分かる。 これと 2 つ目の事実を合わせると、 \displaystyle \frac{\partial ^ 2 f(l, r)}{\partial l \partial r} \leq 0 が従う。 \blacksquare