[yukicoder] No.1292 パタパタ三角形

スポンサーリンク

概要

問題文 →
公式解説 →
自分の提出 →

Fastest AC 記念

解法

まず、正三角形を次のように座標空間内に配置します: A(1,0,0),B(0,1,0),C(0,0,1).

ABC に関する対称移動先は、ABDC が平行四辺形となる D に等しいので、A+B+C に等しいです。したがって、

  • AA+B+C
  • B+AB+C
  • C+A+BC

をしていけば移動を計算できています。三角形の位置は、その重心の座標で代表させることを考えると、各時点での A+B+C を set などに挿入して要素数を数えれば答が得られます。


整数の 3 つ組を適当にハッシュ化することを考えると、次のような解法も得られます。

  • A,B,C をランダムな整数とする
  • AA+B+C 等を繰り返し、A+B+C の種類数を答える。

さらに平行移動・定数倍によって初期値は A=0, B=1 としてよいことも分かります。C を適当な乱数として以上を実装すれば十分な確率で AC が得られます。また、初期値を (0,1,x) とするとき区別したい 1 次式は b+cx(|b|,|c|O(N)) の形であることから、C の初期値を N よりも十分大きくとっておけば、確率に依らず正当な解法となります。

タイトルとURLをコピーしました