Google code jam 2018 Qualification Round 2018
Updated:
Google code jam 2018 Practice Session 2018
疲れている中でよくデバグ頑張ったと思う。
Solutions
Saving The Universe Again
CS を見つけたら SC に置換することでダメージは減る。その逆は増える。ではどの CS を置換するべきであろうか。答えは後ろの方からである。後ろの S ほど多くのダメージを受ける。文字数が $\lvert P \rvert \leq 30$ であるから、愚直にやってもこの $2$ 乗のオーダーである。文字を毎回解析し、逐次トータルダメージを計算すればよろしい。
Trouble Sort
最初頭が働かなくて、乱数でトラブルソートをしてみた。そうして気づいた。なんのことはない。これは $L$ の偶数番目と奇数番目で分けてからバブルソートしてマージしているだけだということに。バブルソートでなくてマージソートすればよくて、すなわち普通にライブラリのソートをすると高速に結果を得ることができる。
Go, Gopher!
$0$-indexed とする。私のアプローチは以下の通り。 $A = 200$ の時は一辺 $L = 15$ の正方形を植林することにする。まず $(1, 1)$ を指定して、 $(0, 0)$ が植林されるまで待つ。こうして $0 \leq i < L-2$ かつ $0 \leq i < L-2$ なる $(i, j)$ に対し、$(i+1, j+1)$ を指定して $(i, j)$が植林されるまで待つ。次に $0 \leq i < L-2$ に対し、$(i+1, L-2)$ を指定して $(i, L-2)$ と $(i, L-1)$ が植林されるのを待つ。逆の軸についても同様にする。最後に $(L-2, L-2)$ を指定して $(L-2, L-2)$, $(L-1, L-2)$, $(L-2, L-1)$, $(L-1, L-1)$ が植林されるのを待つ。
ポイント
どこで植林が終わるかはわからないので、必ず結果を見るようにする。
Cubic UFO
Test set 1 の解法
この場合 $1 \leq A \leq \sqrt{2}$ の解答を書くことになる。平面 $y = -3$ を $P$ と書く。
$z$ 軸を中心に $0 \leq \theta \leq \pi/4$ だけ回転させると、 $P$ への正射影は $1 \times \sqrt{2} \cos (\pi/4 - \theta)$ の長方形となる。つまり $\sqrt{2} \cos (\pi/4 - \theta) = A$ を与える $\theta$ を求めれば答えが出ることになる。加法定理で展開すると $\cos \theta + \sin \theta = A$ となる。 $2$ 乗すると $\cos \theta \sin \theta = (A^2 - 1)/2$ となる。よって $\cos \theta$ と $\sin \theta$ は $2$ 次方程式 $x^2 - Ax + (A^2 - 1)/2 = 0$ の解である。よって、
\[
\begin{align}
\cos \theta &= \frac{A + \sqrt{2 - A^2}}{2}, \
\sin \theta &= \frac{A - \sqrt{2 - A^2}}{2}
\end{align}
\]
と求まる。$z$ 軸を中心とする $\theta$ 回転を表す行列は
\[
R_\theta =
\begin{pmatrix}
\cos \theta & -\sin \theta & 0 \
\sin \theta & \cos \theta & 0 \
0 & 0 & 1
\end{pmatrix}
\]
である。あとは、
\[
p_0 = \begin{pmatrix} 1/2 \\ 0 \\ 0 \end{pmatrix},
p_1 = \begin{pmatrix} 0 \\ 1/2 \\ 0 \end{pmatrix},
p_2 = \begin{pmatrix} 0 \\ 0 \\ 1/2 \end{pmatrix}
\]
として順次 $R_\theta p_i$ を計算し出力するだけである。
Test set 2 の解法
この場合 $1 \leq A \leq \sqrt{3}$ の解答を書くことになる。まずズルをすることにする。以下の動画を見ればわかる通り、 1 辺 $1$ の直方体の $P$ への正射影への面積は、「高さの差」と一致する。この事実を使うことにする。
まず $y$ 軸を中心に $\pi/4$ 回転させることにする。いうまでもなく
\[
R =
\begin{pmatrix}
1/\sqrt{2} & 0 & -1/\sqrt{2} \
0 & 1 & 0 \
1/\sqrt{2} & 0 & 1/\sqrt{2}
\end{pmatrix}
\]
を $p_i$ たちにかけるだけである。あとは 図を見て $z$ 軸方向に $\theta$ 回転させる。
関係式は $\cos(\alpha - \theta) = A/ \sqrt{3}$ である。ここで $\alpha$ は $0 \leq \alpha \leq \pi/2$, $\cos \alpha = 1/\sqrt{3}$, $\sin \alpha = \sqrt{2}/\sqrt{3}$ を充たす角である。これを加法定理で展開し整理すると $\cos \theta + \sqrt{2} \sin \theta = A$ となる。記号を簡略化するため $X = \cos \theta$, $Y = \sin \theta$ とする。すると $X^2 + Y^2 = 1$, $X + \sqrt{2} Y = A$ となる。後者を用いて前者から $X$ を消去すると、 $Y$ についての $2$ 次方程式 $3Y^2 - 2\sqrt{2} A Y + (A^2 - 1) = 0$ が得られる。よって
\[
Y = \frac{\sqrt{2} A - \sqrt{3 - A^2}}{3}
\]
と求まる。解の公式の複号 $\pm$ は $A = 1$ を代入して正しいほう、つまり $Y = \sin 0 = 0$ が出る方、すなわちマイナスを選ぶ。 $A$ は $\theta$ に対して連続的に変化するので突然プラスが答えになることはない。あとは $X = A - \sqrt{2} Y$ とし、
\[
R’ =
\begin{pmatrix}
X & -Y & 0 \
Y & X & 0 \
0 & 0 & 1
\end{pmatrix}
\]
とし、 $R’ R p_i$ を求めて出力すればよろしい。
ポイント
後半は疲れた体と頭だと無理だった。
$A = \sqrt{2}$ の時、数学だと $\sqrt{2 - A^2} = 0$ であるが、計算機だと倍精度浮動点小数であるから実際は $A$ は $\sqrt{2}$ よりごくわずかに大きいまたは小さい。大きい場合は $\sqrt{2 - A^2}$ は NaN になる。これは大変な落とし穴のように思った。正しい解法では問題はないが。
Others
コンテストシステムは不安定なのか、UFO の問題は $3$ 回 submit することになった。問題のないようにしてほしい。
2018/04/10 追記
「復習のために judge system をコンテスト後にも解放してくれ」と GCJ チームにメールしていました。返信は「今の所 open にはしていない」というものでした。 他はともかく、 Cubic UFO は judge system で検査したいところですね。コンテストが終わった後に解放されることを願っています。