問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

縦 $A$ , 横 $B$ の長方形の内部 (及び周) に含まれる正三角形の辺の長さの最大値を求めよ.

制約

$1 \leq A,B \leq 1000$

解法 1

$A \leq B$ を仮定する. また, 以降では座標平面内で考える. $\mathbb{R}^2$ の部分集合 $R$ を長方形 $R:=[0,A] \times [0,B]$ とする.

このとき, $R$ に含まれる長さ $l$ の正方形が存在するならば, 長方形 $R$ の頂点と頂点を共有する長さ $l$ の正三角形が存在する.

(証明)

正三角形のうち, 最も上, 最も下, 最も右, 最も左にある頂点を考えると, 鳩ノ巣原理より, ある頂点がこの中で少なくとも $2$ つの部門を担っている. ここで, 正三角形なので, 最も上かつ最も下になることはない. 最も右かつ最も左もなりえない.

よって, 最も上か最も下から (少なくとも) 一方, 最も右か最も左から (少なくとも) 一方を満たす. 例えば, 最も下かつ最も左ならば, 左下の場合, 左下に平行移動させることで, 正三角形のその頂点を原点 $O$ と一致させることができる. 他の場合も同様である.

ここで, 対称性から, 共有する頂点は原点 $O$ であるとしてもよい.

これ以降, $R$ の原点以外の残りの $3$ 頂点を $S=(A,0), T=(A,B), U=(0,B)$ とし, $R$ は $OSTU$ の順に反時計回りで頂点を成す. また, 正三角形の $O$ 以外の残りの $2$ 頂点を $P,Q$ とし, $x$ 軸正の部分から反時計回りに測る変換が小さい方を $P$ 大きい方を $Q$ とする.

また, $R$ は凸集合であるから, 三角形が $R$ に含まれることと, 三角形の $3$ 頂点全てが $R$ に含まれることは同値である.

このとき, 以下のうち少なくとも一方が成り立つ.

$P$ が線分 $ST$ 上の点になる.
$Q$ が線分 $UT$ 上の点になる.

証明

任意の正三角形 $OPQ$ に対して, $P,Q$ は第 I 象限 (または軸の正の部分) の点である. よって, 線分 $OP,OQ$ を $P,Q$ 側へ同じ比率だけ伸ばすと, $P,Q$ のうち少なくとも一方は線分 $ST$ または線分 $TU$ に当たる.

ここで, $P$ が ( $T$ を除く) 線分 $UT$ に当たったとすると, $A \leq B$ の仮定により, $X$ の偏角が $45^\circ$ を超えてしまう. すると, $Y$ の偏角が $105^\circ$ 以上 $135^\circ$ になってしまい, $Y$ が $R$ の点でなくなってしまう. 点 $Q$ と線分 $ST$ の関係も同様である.

解法 2-(a)

点 $P$ が線分 $ST$ 上の点である場合を考える. このとき, $P$ の偏角を $\theta$ とすると,

$0 \leq \theta \leq 30^\circ$
$P=(A, A \tan \theta)$

となる. このとき,

$Q=\left(\dfrac{A}{2}(1-\sqrt{3} \tan \theta), \dfrac{A}{2}(\sqrt{3}+\tan \theta) \right)$

となる. この $Q$ が $R$ の点になるためには,

$\dfrac{A}{2}(1-\sqrt{3} \tan \theta) \geq 0, \quad \dfrac{A}{2}(\sqrt{3}+\tan \theta) \leq B$

となる. これを解くと,

$0 \leq \tan \theta \leq \min \left(\dfrac{1}{\sqrt{3}}, 2 \times \dfrac{B}{A}-\sqrt{3} \right)$

となる.

このような $\theta$ が存在するための必要十分条件は, $\sqrt{3}A \leq 2B$ である. なお, $A \leq B$ という仮定をしており, $\sqrt{3} \leq 2$ であるから, これは必ず成立する. よって, このパターンを満たすような正三角形は存在する.

さて, このような $\theta$ において, 三角形 $OPQ$ の $1$ 辺の長さは $\dfrac{A}{\cos \theta}$ であるので, $\theta$ が大きいほど長さが長くなる. よって, このパターンにおける最大値は $\displaystyle \Theta_1:=\arctan \min \left(\dfrac{1}{\sqrt{3}}, 2 \times \dfrac{B}{A}-\sqrt{3} \right)$ として, $\dfrac{A}{\cos \Theta_1}$ である.

ここで, 三角関数における相互関係により,

$\displaystyle \dfrac{A}{\cos \Theta_1}=A \sqrt{1+\tan^2 \Theta_1}=A \sqrt{1+\min \left(\dfrac{1}{3}, \left(2 \times \dfrac{B}{A}-\sqrt{3} \right)^2\right)}$

である.

解法 2-(b)

点 $Q$ が線分 $UT$ 上の点である場合を考える. このとき, $\theta:=\angle UOQ$ とすると, 2-(a) における $A,B$ を入れ替えることによって, $\sqrt{3}B \leq 2A$ のとき, このパターンを満たすような正三角形が存在して, この場合における最大値は $\displaystyle \Theta_2:=\arctan \min \left(\dfrac{1}{\sqrt{3}}, 2 \times \dfrac{A}{B}-\sqrt{3} \right)$ として, $\dfrac{B}{\cos \Theta_2}$ である.

ここで, 三角関数における相互関係により,

$\displaystyle \dfrac{B}{\cos \Theta_2}=B \sqrt{1+\tan^2 \Theta_2}=B \sqrt{1+\min \left(\dfrac{1}{3}, \left( 2 \times \dfrac{A}{B}-\sqrt{3} \right)^2 \right)}$