TopCoderOpen 2016 Round2A Easy LCMGCD

Easy落として黄色になってしまった…。
https://community.topcoder.com/stat?c=problem_statement&pm=14095

問題

非負整数(a,b)に対し2^a*3^bの形に素因数分解できる整数群のみからなる整数の集合が与えられる。
これらの集合から2値x,yを抜き出し、LCM(x,y),GCD(x,y)のどちらかを代わりに挿入するという操作を繰り返す。
最終的に集合内を単一の値tにすることができるか判定せよ。

解法

2^a*3^bの形で表現される整数を２次元座標上で(a,b)に対応付けることを考える。
tが(ta,tb)に対応付けられるとする。
LCM,GCDを取るという動作は、２値(a1,b1),(a2,b2)に対し(min(a1,a2),min(b1,b2))か(max(a1,a2),max(b1,b2))のどちらかに差し替えることを意味する。
そして最終的に１つの点(ta,tb)に収束できるか判断することになる。

解法は２つある。
x座標がtaより小さい・taに等しい・taより大きい、y座標がtbより小さい・tbに等しい・tbより大きいで初期状態の点は9通りの位置に分類できる。
細かい数値は置いておいて、９通りの座標にそれぞれ点がある、と考えて遷移を総当たりしてもよい。

また、場合分けで解くこともできる。
元々(ta,tb)に相当する点があるならば、残りの点をすべて消せるか判定すればよい。
(ta,b1),(a2,tb)に対応する点があるならば、前者のx座標、後者のy座標を変化させない範囲で各頂点を移動させ、残りの点をすべて消せるか判定すればよい。

以下のコードは場合分けを頑張っている。

class LCMGCD {
	public:
	
	pair<int,int> sp(int v) {
		pair<int,int> a={0,0};
		while(v%2==0) a.first++,v/=2;
		while(v%3==0) a.second++,v/=3;
		return a;
	}
	string isPossible(vector <int> X, int t) {
		string ret[]={"Possible","Impossible"};
		int N=X.size();
		pair<int,int> T=sp(t);
		vector<pair<int,int>> V;
		
		FORR(r,X) V.push_back(sp(r));
		int i,j,x,y;
		FOR(i,N) if(V[i]==T) {
			if(N==1) return ret[0];
			int L=100,R=-1,D=100,U=-1;
			FOR(j,N) if(i!=j) {
				L=min(L,V[j].first);
				R=max(R,V[j].first);
				D=min(D,V[j].second);
				U=max(U,V[j].second);
			}
			if(L<=T.first&&D<=T.second) return ret[0];
			if(T.first<=R&&T.second<=U) return ret[0];
		}
		FOR(i,N) FOR(j,N) if(i!=j && T.first==V[i].first && T.second==V[j].second) {
			if(((V[i].first<V[j].first)&&(V[i].second>V[j].second)) || ((V[i].first>V[j].first)&&(V[i].second<V[j].second))) {
				return ret[0];
			}
			else if(V[i].first<V[j].first && V[i].second<V[j].second) {
				FOR(x,N) if(i!=x && j!=x && V[x].first<=V[i].first && V[x].second>=V[j].second) return ret[0];
			}
			else if(V[i].first>V[j].first && V[i].second>V[j].second) {
				FOR(x,N) if(i!=x && j!=x && V[x].first>=V[i].first && V[x].second<=V[j].second) return ret[0];
			}
		}
		return ret[1];
	}
}

まとめ

方針はあってたのにしょうもないミスを２つ重ねて落とした。