Mister雑記

競プロやります。

AGC001-B 「Mysterious Light」 (500)

いかに問題を分割するか。

問題リンク

概要

一辺 Nの正三角形状に並んだ鏡の中を、ある一辺上の頂点から距離 Xの箇所から他の一辺に対して平行に光線が放たれる。

この光線には特殊な性質があり、鏡だけでなく過去に自分が通った軌道でも反射する。

この光線が放たれてから、再び放たれた点へ戻ってくるまでに通った軌跡の長さを求めよ。

制約

  •  2 \leq N \leq 10^{12}
  •  1 \leq X \lt N

解説

この問題は、光線の図の中にある平行四辺形の存在を意識できるかどうかが鍵となる。

まず、最初に2回反射すると下図のようになる。 今後は正三角形ではなく、辺の長さが (X, N - X)の平行四辺形のみについて考えればいい。

f:id:misteer:20180918022925p:plain

さて、一般化して辺の長さ (A, B)の平行四辺形について考えよう。ただし A \lt Bと仮定する。 このとき、 B Aの倍数か否かで場合分けする必要がある。

 B Aの倍数でない場合

このときの光の軌跡は以下の通り。右の壁に跳ね返る回数は B / A回なので、光路長は A \times 2(B / A)となる。

さらにまた新たに (B \% A, A)の平行四辺形が出現するので、これについて再帰的に調べることになる。

f:id:misteer:20180918022941p:plain

 B Aの倍数である場合

このときの光の軌道は以下の通りで、光は出発点に帰ってくる。

光路長は先の場合より短くなって A \times (2(B / A) - 1)となる。

f:id:misteer:20180918022957p:plain

以上を再帰関数を使って実装すればいい。

実装例

#include <iostream>
using namespace std;
using ll = long long;

// (A, B)の平行四辺形内での軌道の長さ
ll reflect(ll A, ll B) {
    if (A > B) swap(A, B);

    ll ref = B / A;
    if (B % A == 0) {
        return (ref * 2 - 1) * A;
    } else {
        return ref * 2 * A + reflect(B % A, A);
    }
}

int main() {
    ll N, X;
    cin >> N >> X;
    cout << N + reflect(X, N - X) << endl;
    return 0;
}

意外とコード量は短くなる。再帰関数様々だ。

感想

  • 初見で上に気づくのは今でも相当時間がかかりそう。
  • 別の方針で沼にハマってしまいそうで怖い問題。