概要
Fastest AC 記念
解法
まず、正三角形を次のように座標空間内に配置します： $A(1,0,0), B(0,1,0), C(0,0,1)$.
$A$ の $BC$ に関する対称移動先は、$ABDC$ が平行四辺形となる $D$ に等しいので、$-A+B+C$ に等しいです。したがって、
- $A \gets -A+B+C$
- $B \gets +A-B+C$
- $C \gets +A+B-C$
をしていけば移動を計算できています。三角形の位置は、その重心の座標で代表させることを考えると、各時点での $A+B+C$ を set などに挿入して要素数を数えれば答が得られます。
整数の $3$ つ組を適当にハッシュ化することを考えると、次のような解法も得られます。
- $A, B, C$ をランダムな整数とする
- $A \gets -A+B+C$ 等を繰り返し、$A+B+C$ の種類数を答える。
さらに平行移動・定数倍によって初期値は $A=0$, $B=1$ としてよいことも分かります。$C$ を適当な乱数として以上を実装すれば十分な確率で AC が得られます。また、初期値を $(0, 1, x)$ とするとき区別したい $1$ 次式は $b + cx (|b|, |c| \in O(N))$ の形であることから、$C$ の初期値を $N$ よりも十分大きくとっておけば、確率に依らず正当な解法となります。
