AtCoder ABC #203 : F - Weed

メモリ使用量が気になるよね。
https://atcoder.jp/contests/abc203/tasks/abc203_f

問題

N要素の整数列Aが与えられる。
また、パラメータKが与えられる。

以下の手順を行い、Aを空にすることを考える。

• まず、K個以下任意個の要素を削除する。
• その後、Aが空になるまで、最大値の半分を超える要素を除く、という処理を行う。

後者の処理回数が最小となるもののうち、前者の削除数の最小値を求めよ。

解法

後半について考えると、1回で最大値が半分になるので、後半の処理は高々log(max(A))回しか行わない。
そこで、Aを降順ソートし、以下の値を考えよう。
f(i,a) := Aのprefix i個までを削除するとき、後者の手順をa回用いた場合に、前者の削除数の最小値

解は、f(N,a)≦Kとなる最小のaとその時のf(N,a)を答えればよい。
f(i,a)からの状態遷移だが、

• A[i+1]を前者の手順で取り除く: f(i+1,a)を(f(i,a)+1)で更新する
• A[i+1]～A[j] (jはA[j]がA[i+1]の半分を超えるような最大の添え字)を後者の手順で取り除く: f(j,a+1)をf(i,a)で更新する。

int N,K;
int A[202020];
int tar[202020];

int num[202020][31];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	
	FOR(i,30) FOR(x,N+1) num[x][i]=1<<30;
	
	sort(A,A+N);
	reverse(A,A+N);
	
	num[0][0]=0;
	
	FOR(i,N) {
		if(i) tar[i]=tar[i-1];
		while(tar[i]<N&&A[i]<2*A[tar[i]]) tar[i]++;
		
		FOR(j,30) {
			num[i+1][j]=min(num[i+1][j],num[i][j]+1);
			num[tar[i]][j+1]=min(num[tar[i]][j+1],num[i][j]);
		}
	}
	
	FOR(i,31) if(num[N][i]<=K) {
		cout<<i<<" "<<num[N][i]<<endl;
		break;
	}
	
}

まとめ

遅れて参加したけど何とか間に合ってよかった。