Codeforces #227 Div2. E. George and Cards

Codeforcesっぽい問題。
http://codeforces.com/contest/387/problem/E

問題

1～NのN枚のカードが１列に並んでおり、その並び順が与えられる。
また、このうち(N-K)枚を取り除いたあとのK枚の並び順が与えられる。
(K枚の並びは、元のN枚の並びと矛盾することはない)

(N-K)枚のカードは任意の順で取り除ける。
取り除く際、取り除くカード以上の数字を持ち、かつ取り除くカードを含んだ連続したカードの部分列があれば、その部分列のカード枚数分スコアを加算できる。

適切な順で取り除いたとき得られるスコアを最大化せよ。

解法

カードを取り除く際、取り除くカードより大きい数字のカードが多いほど得なのだから、数字の小さい順にカードを取り除いていけばよい。

カードを取り除く際、より小さい数字でかつ取り除く予定の数字はすでに取り除かれている。
よってスコア加算対象の部分列は、取り除くカードの前後でK枚残す小さいカードのところまで含めることができる。

あとは２つのFenwick Treeを使って処理していく。

• １つは、端からその位置までに何枚カードが残っているか。初期状態では全てのカードが残っているので、i番目の位置までにi枚あるよう初期化する。
• もうひとつは、部分列の位置判定に使うもの。初期状態ではN枚分が全部同じ数字になるようにしておく。

あとは1～Nまで、位置ではなく数値の小さい分に処理する。

• その数字が最後まで残る場合：
  • そのカードは以後スコア加算の対象外なので、１つ目の木の対象位置をデクリメントする
  • 以後、そのカードをまたぐ部分列は作れなくなるので、その前後が別のグループであることを示すため、２つ目の木の対象位置をインクリメントする
• その数字を取り除く場合：
  • ２つ目の木を使って部分列の範囲を求める。２つ目の木において、対象カードの位置と同じ値を持つ位置は部分列の対象となる。
  • ２つ目の木から部分列の範囲を求めたら、１つ目の木でその範囲の有効カードの枚数をカウントする。
  • そのカードは以後スコア加算の対象外なので、１つ目の木の対象位置をデクリメントする

Fenwick Treeの処理がO(logN)なので全体でO(N logN)。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];

	int lower_bound(V val) {
		V tv=0;
		int i,ent=0;
		FOR(i,ME) if(tv+bit[ent+(1<<(ME-1-i))-1]<val) tv+=bit[ent+(1<<(ME-1-i))-1], ent += (1<<(ME-1-i));
		return ent;
	}
	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) s+=bit[entry-1], entry -= entry & -entry;
		return s;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= (1<<ME)) bit[entry-1] += val, entry += entry & -entry;
	}
};
BIT<int,21> cnt,ava;

int N,K;
int rem[1000003];
int ord[1000003];

void solve() {
	int f,i,j,k,l,x,y,r;
	ll ret=0;
	
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>x;
		ord[x]=i+1;
	}
	FOR(i,K) {
		cin>>x;
		rem[x]=1;
	}
	
	FOR(i,N) cnt.update(i+1,1);
	ava.update(1,1);
	ava.update(N+1,1);
	
	FOR(i,N) {
		if(rem[i+1]) {
			cnt.update(ord[i+1],-1);
			ava.update(ord[i+1],1);
		}
		else {
			x = ava.total(ord[i+1]);
			int a=ava.lower_bound(x);
			int b=ava.lower_bound(x+1);
			ret += cnt.total(b-1)-cnt.total(a-1);
			cnt.update(ord[i+1],-1);
		}
	}
	cout << ret << endl;
}

まとめ

本番はC,Dで時間切れ。
解法としては自力で思いつけただけにもったいない。