No.620 ぐるぐるぐるりん 解説
問題
所与の \( T, w, v, g_x, g_y \) に対して、
\( \left( \begin{array}c x_0 \\ y_0 \end{array} \right) = \left( \begin{array}c 1 \\ 0 \end{array} \right) \)
\( \left( \begin{array}c x_{t+1} \\ y_{t+1} \end{array} \right) = \left( \begin{array}{cc} v+1 & -w \\ w & v+1 \end{array} \right) \left( \begin{array}c x_t \\ y_t \end{array} \right) + \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)
\( \left( \begin{array}c x_T \\ y_T \end{array} \right) = \left( \begin{array}c g_x \\ g_y \end{array} \right) \)
を満たし、かつ \( \sum_{t=0}^{T-1} ( u_{x,t}^2 + u_{y,t}^2 ) \) を最小化するような \( u_{x,t}, u_{y,t} \) を求めよ。
解説
\( M = \left( \begin{array}{cc} v+1 & -w \\ w & v+1 \end{array} \right) \)
と置きます。
満たすべき条件は要するに
\( \left( \begin{array}c g_x \\ g_y \end{array} \right) = M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) + \sum_{t=0}^{T-1} M^{T-1-t} \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)
ということです。
\( M \) は拡縮と回転の合成変換となっており、拡縮倍率を表すスカラー \( s = \sqrt{(v+1)^2+w^2} \) と回転を表す行列 \( R = \left( \begin{array}{cc} \cos \theta & - \sin \theta \\ \sin \theta & \cos \theta \end{array} \right) \) を用いて
\( M = s R \)
と表すことができます。
このうち、回転 \( R \) は \( \sum_{t=0}^{T-1} ( u_{x,i}^2 + u_{y,i}^2 ) \) の値に影響しませんから、
\( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) = R^{T-1-t} \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)
と置くと、この問題の条件は
\( \left( \begin{array}c g_x \\ g_y \end{array} \right) - M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) = \sum_{t=0}^{T-1} s^{T-1-t} \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) \)
を満たし、かつ \( \sum_{t=0}^{T-1} ( u'_{x,t}^2 + u'_{y,t}^2 ) \) を最小化すると言い替えることができます。
これは、成分ごとに考えれば単なるスカラーの問題として解くことができて(*1)、
\( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) = \cfrac{s^{T-1-t}}{\sum_i s^{2(T-1-i)}} \left( \left( \begin{array}c g_x \\ g_y \end{array} \right) - M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) \right) \)
となります。
あとは \( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) \) から \( \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \) を復元すれば完成です。
--------
(*1) 球と平面の接点の問題（原点 \( (0,0,0) \) を中心とする球が平面 \( ax+by+cz=d \) に接しているとき、その接点の座標を求めよ）の考え方で解くことができます。
感想
というわけで、ほぼ高校数学の範囲で厳密解を求めることができて、あとは具体的な数値を代入するだけですので、これで★4.5は過大気味ではないかとも思いましたが、実際に解けている人が非常に少なく、強い人も苦労しているようですので、競技プログラミング的には難しい問題のようですね。
