Ad Infinitum 17: The Axis of Awesome
変なことを言ってたらごめんなさい。
https://www.hackerrank.com/contests/infinitum17/challenges/the-axis-of-awesome
解法
ある軸 $a=(u,v,w)$ と点 $r=(x,y,z)$との距離は外積を用いて $|a \times r|$ で計算できる。このことを用いると、距離の二乗和というのは慣性テンソル $I$ を用いて $ x^{\mathrm{T}} I x$ と表せることが分かる。
座標系は自由に取っていいので、$I$ が対角行列になるような座標系で考えよう。$I$は対称行列なので、このような座標系はかならず取れる。$ x^{\mathrm{T}} I x$ が任意の $x$ で等しくなるためには $I=\lambda E$ の形をしていればよい。つまり、固有値が一通りしかなければ良い。
（以降は基本的に新しい座標系で話をすすめる）
点を一個加えたときの $I$ は
$$ I=\begin{pmatrix} \lambda_1 + y^2+z^2 & -xy & -xz \\ -xy & \lambda_2 + x^2+z^2 & -yz \\ -xz & -yz & \lambda_3 + x^2+y^2 \end{pmatrix} $$
となる。これが固有値を一種類しか持たなければ成功だが、そのためには$I=\lambda E$ の形をしていなければならない。すなわち $xy=xz=yz=0$ が要求される。これは$x,y,z$ のなかの非ゼロ要素が 1 つしかないことを意味する。
もし $\lambda_1=\lambda_2=\lambda_3$ だった場合、点を加える必要はない。答えは 0 である。
もし $\lambda_1=\lambda_2<\lambda_3$ だった場合、$(0,0,z)$をうまく追加することで $\lambda E$ の形にできる。ゆえに答えは 1 である。
もし $\lambda_1<\lambda_2<\lambda_3$ だった場合、明らかに $\lambda E$ の形にはできない。$(0,y,0)$を追加すると $\lambda_1=\lambda_2<\lambda_3$ のケースに帰着できる。ゆえに答えは 2 である。
もし $\lambda_1<\lambda_2=\lambda_3$ だった場合、$(0,0)$要素の値を上げようとすると $(1,1),(2,2)$ のどちらかが上がってしまうため、一回は不可能である。$\lambda_1=\lambda_2<\lambda_3$ のケースに帰着できる。ゆえに答えは 2 である。
もとの座標系における $I$ の固有多項式について調べてあげれば良い。やることは受験数学によくありそうなものなので、使う性質だけ書いておく。
久しぶりにまともな線形代数を使った気がする。
