AGC001-B：Mysterious Light

問題

https://beta.atcoder.jp/contests/agc001/tasks/agc001_b

正三角形上に光を当てて、反射するときの距離の問題

考え方

以下の図のように光のがどのように進むか法則性がわかると見通しがよい。

光の始点を A とする。この光は C で反射し点 B へ進む。平行四辺形ACBDでBを始点にして光が進む時の距離は、点 E で反射し点 F へ進む。つまり平行四辺形のある点から進む光の距離は 2 回反射すると形が小さくなった別の平行四辺形のある点に進む。よって平行四辺形の短辺を a 、長辺を b とする平行四辺形から進む光の距離 func(a, b) は、

func(a, b) = 2a + func(a, b - a)

となる。再帰的にサイズが小さくなるので求めることができた。

ナイーブに実装すると、 b が a に対して非常に大きい数になると、時間内に求めることができない。a が b を割り切らない時、反射の回数は b/a となるので、

func(a, b) = 2(b/a)a + func(a, b % a)

で求めることができる。a が b を割り切る時は、反射の数が 1 回少なくなる。(最後にピッタリおさまるため)

       public void solve(int testNumber, InputReader in, PrintWriter out) {
 
            long n = in.nextLong(), x = in.nextLong();
            long ans = n + f(n - x, x);
            out.println(ans);
        }
 
        long f(long a, long b) {
            if (a > b) {
                long t = b;
                b = a;
                a = t;
            }
            if (b % a == 0) return 2*(b/a-1)*a;
            return 2*(b/a)*a + f(a, b % a);
        }

ポイント

• 再帰
• 共通するパターンを考える

類題