いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AtCoder Grand Contest 001 B - Mysterious Light

解法

正三角形に入った光が2回反射した後の形を考えると平行四辺形になる
また反射2回分の光の長さはNになる
f:id:ratetion:20180725205352p:plain
後はその中で何が起こるかを考える
ここからも2回ずつ反射が起こった時の動きを考える
残った平行四辺形の辺をa,b(a < b)とすると,2回反射後の平行四辺形はa,b-2aになり,光の長さは2aになる
これをa=bになるまで求め最後に1回分のaを足せば答えになる
計算量はO(N)で,これで部分点が得られる
Submission #2903541 - AtCoder Grand Contest 001

2回反射後の平行四辺形においてabの大小関係が変わらない限り同じ計算が続くことに着目すると計算量が減らせる
計算量がO(logN)で満点が得られる
Submission #2903572 - AtCoder Grand Contest 001

そのまま書いたのでswap部分は許して

gcdと同じことが起きてるらしいがその感覚はまだ養えてない感じがした