kmjp's blog

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

HackerRank HourRank 24 : C. Mutual Indivisibility

残念。
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");
		}
	}
}

まとめ

確信ないまま出して通ってしまった…。