読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

AtCoder Grand Contest 001: B. Mysterious Light

http://agc001.contest.atcoder.jp/tasks/agc001_b

解法

2 回の反射で平行四辺形ができる。

f:id:pekempey:20160718030114p:plain:w400

さらに 2 回反射させても平行四辺形ができる。

f:id:pekempey:20160718034826p:plain:w300

A<B であれば平行四辺形の辺の長さは(A,B)→(A,B-A) のように変化する。互除法と同様に、(A,B)→(A,B mod A) のようにできる。

f:id:pekempey:20160718034843p:plain:w300

計算量は対数時間になので、これで間に合う。

工夫すると綺麗な式がでると信じてたので互除法に気づくのが遅れた。結局、綺麗な式はあったし苦手感がある問題だった。