☆幾何( AGC001B - Mysterious Light)

新元号令和おめでとうございます。

atcoder.jp
うわ苦手…

最初は三角形に対して光を射出してるけど、そのあとは光の軌跡によって区切られた平行四辺形に対して射出していると考えて良さそう。ここから解法をひねり出します。

この時両辺がa,b(a>=b>0)の平行四辺形に光を発車した時、その光の奇跡の長さをf(a,b)とするととして良い。ただしa=bになった時は、a進んでから以下のように考える。
a進んだ先が射出地点だった時…これでゴール。
a進んだ先が射出地点以外だった時…今までの道を通って射出地点に戻ってくる。
なんだけど、よく考えると進んだ先が射出地点でないことはありえない。これは説明が難しいけど、図を見れば射出地点にどんどん近づいていくことがわかるし、光の角度を追っていくと左上方向の光以外が平行四辺形の角に当たることはない。よってこれでゴールとしてしまって良い。

これってgcd求める時のユークリッドの互除法に似ているな。おそらく、ここで一回一回再帰を呼び出すとTLEするのだろう。%でやれば計算量はだいたい10の指数に比例するので間に合う。
と表せるのでこの方法は可能である。
というわけで、再帰ループを回せば良い。

floorを求めるところで念のために(int)をつけてたけど(long long int)にしなければならず1WA。
解説見たら別解としてめっちゃ綺麗な解法あってびびった。

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>

 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long

ll int f_shikaku(ll int A,ll int B){
    ll int a=max(A,B);
    ll int b=min(A,B);
    if(a%b==0)return 2*(ll int)(a/b)*b-b;
    return f_shikaku(a%b,b)+2*(ll int)(a/b)*b;
}
int main(void){
    ll int N,X;
    scanf("%lld %lld",&N,&X);
    ll int ans;
    ans=f_shikaku(X,N-X)+N;
    printf("%lld\n",ans);
}