Codeforces #168 Div1. A. k-Multiple Free Set

さてここからが本番のDiv1。
http://codeforces.com/contest/274/problem/A

問題

N個の整数と、整数Kが与えられる。
N個の整数のサブセットのうち、任意の２値が互いにK倍の差が無いようにしたい。
そのようなサブセットの最大要素数を答える。

回答

N個の整数をソートして、小さい数から順にNG集合にない物をサブセットに入れるとしてカウントする。
その際、ある数Aをカウントした場合、A*KをNG集合に追加していけばよい。

int N,K;
vector<ll> A;
set<ll> NG;

void solve() {
	int f,r,i,j,k,l, x,y,loop;
	ll LH,CL,hoge;
	
	N=GETi();
	K=GETi();
	FOR(i,N) A.push_back(GETi());
	sort(A.begin(),A.end());
	j=0;
	FOR(i,N) {
		if(NG.find(A[i])==NG.end()) {
			j++;
			NG.insert(A[i]*K);
		}
	}
	_P("%d\n",j);
	
	return;
}

まとめ

一見、K=2の時に2,4,8,16,32のリストに対し2,8,32と4,16どちらを取ろうか迷ったが、小さい方からgreedyに取ればいいのね。
人によってはちゃんと2,8,32と4,16どちらを取るのがいいかDFS等使って検索していた。