Codeforces #889 : Div1 B. Earn or Unlock

割と変な配点だな。
https://codeforces.com/contest/1854/problem/B

問題

N毎のカードの山があり、それぞれ非負整数が書かれている。
この山は、最上位の1枚だけアンロックされており、それ以外はロックされている。
この山に対し、以下の処理を行う。

• 山にカードがない、または最上位のカードがロックされている場合処理を終える。
• そうでない場合、カードの値をvとして以下のいずれかを行う。
  • カードの山のうちロックされているカード上からv枚アンロックする
  • v点を得る
• その後、そのカードは破棄する。

最適な手順を取る場合、得られる得点の最大値を求めよ。

解法

Bitsetで対応する。

f(x) := x枚目までアンロックされた状態を作るのに、アンロックに回すカードの値の総和のうちx以上の最小値
これはBitsetを使い、ちょうどx枚目までアンロックされた状態を作れるかどうか管理することで、Bitsetに対し先頭のbitを求めることで算出できる。
g(x) = 先頭x枚の値の総和
とすると、g(x)-f(x)の最大値が解となる。g(x)はO(1)で求められるので、f(x)をbitsetでO(N^2/w)で求めればよい。

int N,A[102020];
bitset<202020> BS;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	BS[1]=1;
	ll sum=1;
	ll ma=0;
	FOR(i,N) {
		cin>>x;
		
		y=BS._Find_first();
		if(y==202020) break;
		sum+=x;
		ma=max(ma,sum-y);
		BS=BS|(BS<<x);
		BS[i+1]=0;
		
	}
	cout<<ma<<endl;
}

まとめ

bitsetが想定解なのは想定外だった。