残念。
https://www.hackerrank.com/contests/hourrank-24/challenges/mutual-indivisibility
問題
整数A,B,Xが与えられる。
[A,B]の範囲の整数の集合で、2要素が互いに片方が片方の倍数にならないようなものをのうち、要素数がXの物を構築せよ。
解法
とりあえず最大数構築して、X個答えればよい。
[A,B]の範囲で上から順に集合に残すか考えていこう。
今x∈[A,B]を残すか考える。
- 集合内にxの倍数が2個以上あるなら、xを加えることで要素が2個へるのでxは残さない。
- 集合内にxの倍数が1個あるなら、xを加え倍数を取り除く。他の要素の倍数になりにくいということで、同じ要素数なら小さい方を残した方がよい。
- 集合内にxの倍数がないなら、xを残す。
int T; int A,B,X; int ok[10101]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>A>>B>>X; ZERO(ok); for(x=A;x<=B;x++) ok[x]=1; for(x=B;x>=A;x--) { int num=0,p=-1; for(y=2*x;y<=B;y+=x) if(ok[y]) { p=y; num++; } if(num>=2) ok[x]=0; if(num==1) ok[p]=0; } vector<int> V; for(x=A;x<=B;x++) if(ok[x]) V.push_back(x); if(V.size()>=X) { FOR(i,X) _P("%d%c",V[i],(i==X-1)?'\n':' '); } else { _P("-1\n"); } } }
まとめ
確信ないまま出して通ってしまった…。