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か迷う問題。
すんなり解法にたどり着けて良かった。