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; } }
まとめ
途中の要素をあえて抜いた方がいい例に気づかず、連続した要素を抜き出して失敗。
同じミスした人はちらほらいた模様。
問題文誤読でもない早とちりでもったいない。