Google Code Jam 2019 Round 2 : C. New Elements : Part2

これは解けなくてもしょうがないかな…。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051679/0000000000146184

問題

Part1と同じ、2種類の原子からなる分子に関する問題である。
Google Code Jam 2019 Round 2: A. New Elements: Part1 - kmjp's blog

Part1と異なり、こちらは分子の重さ順は入力で与えられている。
ここで、条件を満たす両原子の重さの比率を整数比で表すとき、前者が最小となるものを求めよ。

解法

Part1と同じ表記をすると、(p,q)＜(P,Q)であるとき、両原子の重さの日がx:yであるならpx+qy＜Px+Qyでなければならない。
ここから、y/xがとりえる下限・上限が確定する。

もちろん、下限と上限の間に正の長さの区間が無ければ解なしである。
そうでない場合、s,t,S,Tがわかっている場合、s/t＜y/x＜S/Tとなるような最小の整数xを求める問題となる。

EditorialではWikipediaにあるアルゴリズムが載っているが、あれは区間が閉区間であればそのまま適用できるが、解区間だとそうはいかない。
(例えば3＜y/x＜4となるy/xを求めようとすると、このアルゴリズムだとy/x=4になってしまう)

そこで別の解法で再帰的に求める。

• s/t＜1＜S/Tの場合、y=x=1が最良。
• 1≦s/t＜S/Tの時、u=floor(s/t)として、(s/t-u)＜(y/x-u)＜(S/T-u)となるy/xを再帰的に求める。
• s/t＜S/T≦1の時、分子と分母を反転してT/S＜x/y＜t/sとなるx,yを再帰的に求める。

なお、分母が0の時は実質∞とみなそう。

int N;
ll C[11],J[11];

ll miP,miQ;
ll maP,maQ;

pair<ll,ll> hoge(ll p1,ll q1,ll p2,ll q2) {
	if(q1==0) q1=1,p1=1LL<<30;
	if(q2==0) q2=1,p2=1LL<<30;
	if(p1<q1 && p2>q2) {
		return {1,1};
	}
	else if(p1>=q1) {
		ll d=p1/q1;
		auto p=hoge(p1-d*q1,q1,p2-d*q2,q2);
		p.first+=d*p.second;
		return p;
	}
	else {
		auto p=hoge(q2,p2,q1,p1);
		return {p.second,p.first};
	}
	
	
}


void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>C[i]>>J[i];
	
	miP=maQ=1;
	miQ=maP=1LL<<30;
	
	FOR(y,N) FOR(x,y) {
		if(C[x]>=C[y] && J[x]>=J[y]) return _P("Case #%d: IMPOSSIBLE\n",_loop);
		if(C[x]>C[y]) {
			ll p=C[x]-C[y];
			ll q=J[y]-J[x];
			if(p*miQ>q*miP) miP=p, miQ=q;
		}
		else if(J[x]>J[y]) {
			ll p=C[y]-C[x];
			ll q=J[x]-J[y];
			if(p*maQ<q*maP) maP=p, maQ=q;
		}
	}
	if(miP*maQ>=maP*miQ) return _P("Case #%d: IMPOSSIBLE\n",_loop);
	
	auto p=hoge(miP,miQ,maP,maQ);
	_P("Case #%d: %lld %lld\n",_loop,p.second,p.first);
}

まとめ

Dより難しくない？