ARC 004
Table of Contents
https://atcoder.jp/contests/arc004
A. 2点間距離の最大値 ( The longest distance )
https://atcoder.jp/contests/arc004/tasks/arc004_1
B. 2点間距離の最大と最小 ( Maximum and Minimum )
https://atcoder.jp/contests/arc004/tasks/arc004_2
C. 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )
https://atcoder.jp/contests/arc004/tasks/arc004_3
解説 AC.
解説の補足
$X, Y$ を $\gcd(X,Y)$ で割って互いに素な整数とする。
\begin{align*} &\frac{X}{Y} = \frac{\frac{1}{2}N(N+1) - M}{N} = \frac{N(N+1) - 2M}{2N} \\ \therefore ~~~ &2NX = \left\{ N(N+1) - 2M \right\} Y \\ \therefore ~~~ &2NX = \left\{ N(N+1) - 2M \right\} Y = kXY ~~~ (k \in \mathbb{Z}, \because \gcd(X,Y) = 1) \\ \therefore ~~~ &\left\{ \begin{aligned} & 2N = kY \\ & N(N+1) - 2M = kX \end{aligned} \\ \right. \end{align*}
$X, Y, N > 0$ だから $k > 0$. また $0 < M \leq N$ だから
\begin{align*} &-2N \leq -2M < 0 \\ \therefore ~~~ &N(N+1) - 2N \leq N(N+1) - 2M < N(N+1) \\ \therefore ~~~ &N^2 - N \leq N(N+1) - 2M < N^2 + N \\ \therefore ~~~ &N^2 - N \leq kX < N^2 + N \\ \therefore ~~~ &\left( \frac{kY}{2} \right)^2 - \frac{kY}{2} \leq kX < \left( \frac{kY}{2} \right)^2 + \frac{kY}{2} \\ \therefore ~~~ &( kY )^2 - 2kY \leq 4kX < ( kY )^2 + 2kY \\ \therefore ~~~ &\frac{4X}{Y^2} - \frac{2}{Y} < k \leq \frac{4X}{Y^2} + \frac{2}{Y} \end{align*}
$k_1 = \frac{4X}{Y^2} - \frac{2}{Y}$, $k_2 = \frac{4X}{Y^2} + \frac{2}{Y}$ とすると $k_2 - k_1 = \frac{4}{Y}$. $1 \leq Y \leq 10^9$ であるから $\frac{4}{Y} \leq 4$. よって $k$ の自由度は生成4である。