pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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$ の固有多項式について調べてあげれば良い。やることは受験数学によくありそうなものなので、使う性質だけ書いておく。

  • 対称行列の固有値は実数のみ。これを使うことで虚数解を持ちそうなグラフの形は考慮する必要がなくなる。
  • 重解を持つとき、その解は極値をとっていて、その極値の点ではx軸に接している。
久しぶりにまともな線形代数を使った気がする。