はまやんはまやんはまやん

hamayanhamayan's blog

Mysterious Light [AGC 001 : B]

問題

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

かなり説明しにくいのでリンクをご覧ください。。。

考察

1. 幾何問題として考えるにはむずすぎる気がする
2. 再帰的に解けるのでは??
3. (コンテスト後にTwitterを見ると、強い人は「ユークリッド系問題かな?」と思うみたいです)
4. (実際そうだからすごい)

5. 再帰的に解くのはいいのだけれど、引数はどうしようか

6. 今回は斜めに動いているが、2直線上でしか動いていない
7. つまり、直線bcをx軸、直線baをy軸と見立てて考えみる

8. あと、もう一つ大切なことが、光の線が増えるたびに光の線が移動できる範囲が狭まる
9. 範囲が狭まる -> 再帰的に解けそう

10. ここまでくればもう一歩
11. 問題文の図を見ると、最初の2回の光の遷移後は、平行四辺形になっている
12. その後2回の遷移でまた平行四辺形。そのまた2回の遷移で平行四辺形。。。
13. 平行四辺形について再帰的に求めればいい!

14. 以下の様な再帰を考えれば良い

rec(int x, int y) : 平行四辺形のx軸方向の長さx,y軸方向の長さyで、これ以降の遷移での光の軌跡の長さ

x < y : return rec(x, y - x) + x * 2
x > y : return rec(x - y, y) + y * 2
x = y : return x

15. 実際、これで作るとTLEする
16. 原因は、x <<< y(xよりyが凄い大きいってこと) の時なので、その場合は遷移をまとめてやる必要がある

実装

http://agc001.contest.atcoder.jp/submissions/808778

typedef long long ll;
ll N, X;
//-----------------------------------------------------------------
ll solve(ll x, ll y) {
	if (x == 0 || y == 0) return 0;
 
	if (x < y && y % x == 0) return (y / x) * x * 2 - x;
	if (y < x && x % y == 0) return (x / y) * y * 2 - y;
 
	if (x < y)
		return solve(x, y - (y / x) * x) + (y / x) * x * 2;
	else if (x > y)
		return solve(x - (x / y) * y, y) + (x / y) * y * 2;
	else
		return x;
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> X;
	ll ans = solve(X, N - X) + N;
	cout << ans << endl;
}