プログラミングコンテストチャレンジブックの「気楽にウォーミングアップ」でさらっと解説されてる Ants(POJ No.1852) を数式に落とすとどうなるのか試してみた。最小値の方だけ書いてみたけど、このままだとプログラミングの勉強も進まないので、最大値はその気になったら書く。
長さLcmの竿の上をn匹のアリが毎秒1cmのスピードで歩いています。
アリが竿の端に到達すると竿の下に落ちていきます。
また、竿の上は狭くてすれ違えないので、二匹のアリが出会うと、
それぞれ反対を向いて戻っていきます。
各アリについて、現在の竿の左端からの距離x_iはわかりますが、
どちらの方向を向いているのかはわかりません。
すべてのアリが竿から落ちるまでにかかる
最小の時間と最大の時間をそれぞれ求めなさい。
制約
1 <= L <= 10^6
1 <= n <= 10^6
0 <= x_i <= L
L, n, x_i はすべて整数値
原題には書いてないですが、
向き・位置が同じ蟻がいた場合を弾くため x_i はすべて相異なるとしておきます。
問題の定式化
$L$, $n$, $x_i(i=1,...,n)$は定数とし、以下の議論では固定する。
この問題で問われている最小値は(1)で表される。
$$
\begin{equation}
\min_{d=(d_1,...d_n) \in \{Left, \ Right\}^n } \ \max_{i=1,...,n} f_i(d) \tag{1}
\end{equation}
$$
関数 $f_i$ は、$i=1,...,n$ について、$(Right,Left)$のいずれかの向き$d_i$を向く蟻 $A_i$ が、竿の端点まで到着する時刻（整数）を表す。
最小値を求める。
証明の方針：下界を求め、その値を実現するベクトル $d$ を構成することで、その下界が最小値であることを示す。
STEP1： 下界を求める。
$d$ , $i$ を任意の値にとる。$A_i$の左端までの距離 $x_i$ と、右端までの距離 $L-x_i$ のうち、短い方 $(=\min(x_i,L-x_i))$ 未満の距離を $A_i$ が歩いても、 $A_i$ が竿から落ちることない。よって以下の不等式が成立する。この式は $x_i=0$ の場合も成立する。
$$
\min(x_i,L-x_i) \leq f_i(d)
$$
この両辺に $\min_{d=(d_1,...d_n) \in \{Left, \ Right\}^n }\max_{i=1,...,n}$ を施しても不等号の向きは変わらないことと、左辺は $d$ の選択に依存しないことから式(1)の下界を得る。
$$
\max_{i=1,...,n} \min(x_i,L-x_i) \leq \min_{d=(d_1,...d_n) \in \{Left, \ Right\}^n }\max_{i=1,...,n} f_i(d) \tag{2}
$$
次に、この式の左辺が最小値であることを示す。
$$
\newcommand{\argmax}{\mathop{\rm arg~max}\limits}
\newcommand{\argmin}{\mathop{\rm arg~min}\limits}
$$
STEP2： 下界を実現する蟻の向きを構成する。
まず
LR_{min}(x) := \left\{
\begin{array}{ll}
Left & \big( x \leq \frac{L}{2}\big) \\
Right & \big( x > \frac{L}{2}\big)
\end{array}
\right.
$$
d_{min}:=(LR_{min}(x_i))_{i=0,...,n}
$$
と定義する。この値を蟻の向きのベクトル $d$ に選択する。このとき
$x_i \leq \frac{L}{2}$ を満たす $i$ の集合 $\it{I_L}$ について、蟻の速度は一定であることから以下が成り立つ。
$$
f_i(d_{min})=x_i=\min (x_i ,L-x_i) \ \ ( \ \forall i \in \it{I_L} \ )
$$
同様に $x_i > \frac{L}{2}$ を満たす $i$ の集合 $\it{I_R}$ について以下が成り立つ。
$$
f_i(d_{min})=L-x_i=\min (x_i ,L-x_i) \ \ ( \ \forall i \in \it{I_R} \ )
$$
が成立する。以上から
$$
f_i(d_{min})=\min (x_i ,L-x_i) \ \ ( \ i={1,...,n} \ )
$$
が成り立つ。よって
$$
\max_{i=1,...,n} f_i(d_{min}) = \max_{i=1,...,n} \min(x_i,L-x_i)
$$
この式はベクトル $d=d_{min}$ の選択が、(2)の左辺の下界の値を実現することを意味する。
以上から(2)の下界が最小値であることが示された。