Google Code Jam 2019 Round 2 : A. New Elements : Part1

うーむ、通るには通ったけど色々いまいちな出来。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051679/0000000000146183

問題

C,J2種類の原子で構成される分子N種類について、両原子の数が与えられる。

両原子の重さの比率がなんだかわからないとき、N個を重さが狭義単調増加の順に並べる並べ方は何通りか。

解法

(p,q) := Cがp個、Jがq個で構成される分子の重さ、とする。
(p,q)と(P,Q)を比べたとき、p≦Pかつq≦Qの関係にあるなら、比率に関わらず両者の大小関係は確定する。
一方p＜Pかつq＞Qや、その逆の場合、比率によって大小関係が変わる。

(p,q)=(P,Q)となる比率があるとき、そこから少しでも比率が大小に動いたら両者の大小関係が確定する。

さて、分子の対について総当たりし、(p,q)=(P,Q)となる比率を列挙しよう。
両者の比率が任意の正の実数を取るとした場合、前述の比率がm通りあると、正の実数は(m+1)個の区間に分けられる。
同一区間内では、分子の大小関係は固定されるので、解は(m+1)通り、と言える。

int N;
pair<ll,ll> P[303];



void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>P[i].first>>P[i].second;
	
	set<pair<ll,ll>> V;
	FOR(x,N) FOR(y,N) if(P[x].first<P[y].first && P[x].second>P[y].second) {
		ll a=abs(P[x].first-P[y].first);
		ll b=abs(P[x].second-P[y].second);
		ll g=__gcd(a,b);
		a/=g,b/=g;
		V.insert({a,b});
	}
	
	_P("Case #%d: %d\n",_loop,V.size()+1);
}

まとめ

まぁこれは本番すぐ思いつけたのでよかったね。
しょうもない1ミスしたけども。