kmjp's blog

競技プログラミング参加記です

Codeforces #323 Div1 A. GCD Table

CFの色基準変更でオレンジになったものの、今回良い順位で赤に復活。
http://codeforces.com/contest/582/problem/A

問題

N要素の整数列A[i]があったとする。
G[i][j]=GCD(A[i],A[j])で構成される2次元配列を考える。

入力として、N及びGの各要素を順不同で与えられる。
元のA[i](順不動)を復元せよ。

解法

GCD(A[x],A[x])=A[x]なことを用いて、大きい順に決めていく。

ここまで判明したAの要素をA[0..(i-1)]とする。
残されたGの最大要素をpとすると、GCD(A[i],A[i])=pよりA[i]=pとなる。

この後Gから、判明している分のAの要素から生成される分、すなわち以下を消す。

  • pを1個消す。
  • GCD(A[i],A[x]) (0≦x<i)を2個ずつ消す。問題文の2次元配列を見てわかるとおり、x!=yならGにはGCD(A[x],A[y])が2個ずつ含まれるので、2個消さなければならない。

上記をAがN個判明するまで繰り返す。

int N;
map<int,int> M;
vector<int> R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N*N) cin>>x, M[-x]++;
	
	while(M.size()) {
		auto r=M.begin();
		if(r->second==0) {
			M.erase(r);
			continue;
		}
		
		x = -r->first;
		FORR(rr,R) M[-__gcd(x,rr)] -= 2;
		M[-x]--;
		R.push_back(x);
	}
	
	FORR(r,R) _P("%d ",r);
	_P("\n");
}

まとめ

これは500ptか750ptか迷う問題。
すんなり解法にたどり着けて良かった。