kmjp's blog

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

TopCoder SRM 684 Div1 Easy CliqueParty

Easy早とちりするしMediumは解けないしグダグダ。3Hackで少し傷を浅くした。
https://community.topcoder.com/stat?c=problem_statement&pm=14171

問題

整数集合がk-クリークであるというのは、集合中の任意の2要素A,Bに対しA≦k*Bを満たすものを指す。
整数集合Sが好みというのは、集合中の任意の2要素P,Qに対し、その差|P-Q|を集めた集合Dを考えたとき、Dがk-クリークであるものを指す。

ここで整数集合Aが与えられる。
Aの部分集合のうちで、好みであるものの最大要素数を求めよ。

解法

Aの部分集合のうち、2要素の差の最大値が、最小値のk倍以下であれば良い。

Aをソートし、まず最小要素A[x]・最大要素,A[y]を総当たりしよう。
あとはその2要素の間の要素において、差が(A[y]-A[x])/k以上となるものだけをAに取り込んでいけば良い。
これはDPでも良いし、貪欲に前の要素からもA[y]からも(A[y]-A[x])/k以上離れた要素を取り込んでいっても良い。

class CliqueParty {
	public:
	int maxsize(vector <int> A, int k) {
		int N=A.size();
		sort(A.begin(),A.end());
		int ret=1;
		int x,y,a,b;
		FOR(y,N) FOR(x,y) {
			int ma=A[y]-A[x];
			int cnt=2;
			int pre=A[x];
			for(int i=x+1;i<y;i++) {
				if(1LL*(A[i]-pre)*k>=ma && 1LL*(A[y]-A[i])*k>=ma) cnt++,pre=A[i];
			}
			ret=max(ret,cnt);
		}
		return ret;
	}
}

まとめ

途中の要素をあえて抜いた方がいい例に気づかず、連続した要素を抜き出して失敗。
同じミスした人はちらほらいた模様。

問題文誤読でもない早とちりでもったいない。

広告を非表示にする