Codeforces #576 Div1 A. MP3

ダメダメだった回。
https://codeforces.com/contest/1198/problem/A

問題

N要素の数列を圧縮してディスクに書きたい。

値を[L,R]に限定することを考える。
その際、L未満の要素はL、Rを超える要素はRにクリップされる。
この時、[L,R]内で異なる値がK通りあるとき、このデータの保存にはN*ceil(logK)ビットかかることになる。

全体をIバイト=8Iビットに収めたい。
その際、クリップで値が変化する要素数を最小にしたい。
最少何要素変更すればよいか。

解法

まず要素をソートしたうえ座標圧縮する。
座標圧縮していれば、Lが決まればRも一意に決まるので、Lを総当たりしていき、[L,R]の範囲外の要素数の最小値を求めればよい。

int N,K;
int A[1010100];
int C[1010100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	int B=8*K/N;
	
	int ok=(B>30)?(1<<20):1<<B;
	
	sort(A,A+N);
	int mi=1<<20;
	
	for(i=1;i<N;i++) C[i]=C[i-1]+(A[i]!=A[i-1]);
	FOR(i,N) {
		x=lower_bound(C+i,C+N,C[i]+ok)-C;
		mi=min(mi,i+N-x);
	}
	cout<<mi<<endl;
	
}

まとめ

やる内容はともかく、問題設定が無駄にややこしく感じる。