kmjp's blog

競技プログラミング参加記です

CSAcademy Round #44 : E. Array Elimination

まぁまぁの時間で解けました。
https://csacademy.com/contest/round-44/task/array-elimination/

問題

数列Aが与えられる。
初期状態ではポインタが先頭要素を指している。

以下の処理をAが空になるまで繰り返すことを考える。

  • ポインタを隣接要素に動かす。
  • ポインタが指す要素を削除する。削除後、ポインタは前後いずれかの要素を指すようにできる。

削除する要素の値が昇順になるように処理を行うとすると、最小処理回数はいくつになるか。

解法

Aの要素を重複なしで昇順に並べたとき、i番目に大きな値と等しい要素を、iステップ目ですべて削除する、ということを考える。
この時、iステップ目で最後に削除するのはiステップ目で削除すべき要素のうち最も手前か最も後ろにあるものとするのが最適である。
あえて手前や後ろでない要素を最後にする理由はない。

よって、iステップでは、(i-1)ステップで消したの両端の要素からiステップで両端の要素を消すまでの最小処理回数を求めよう。
処理を進めると数列中の要素が徐々に減っていくので、BITを使い要素間を辿る際のポインタの移動回数を計算しよう。

(i-1)ステップで最後に消した要素が、iステップで消すべき要素群の両端に挟まれている場合、先に手前を消したのち戻ってきて最後後ろの要素を消すケースと、その逆のケースがあるので注意。
行ったあと戻る際は、行きの時点で要素を消していくので戻る方は処理回数が減ることに注意。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt,bt2;

int N;
int A[101010];
vector<int> V;
vector<int> ev[101010];
ll ret[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i],V.push_back(A[i]), bt.add(i,1), ret[i]=1LL<<60;
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	
	FOR(i,N) ev[lower_bound(ALL(V),A[i])-V.begin()].push_back(i);
	ret[ev[0].back()]=ev[0].back()+1;
	
	FOR(i,V.size()-1) {
		FORR(e,ev[i]) bt.add(e,-1);
		FORR(e,ev[i+1]) bt2.add(e,1);
		FORR(e,ev[i]) if(ret[e]<1LL<<60) {
			x=ev[i+1][0];
			y=ev[i+1].back();
			
			if(e<x) {
				ret[y]=min(ret[y],ret[e]+(bt(y)-bt(e)));
			}
			else if(y<e) {
				ret[x]=min(ret[x],ret[e]+(bt(e)-bt(x-1)));
			}
			else {
				// e->x->y
				int goleft=bt(e)-bt(x-1);
				int goright=bt(y)-bt(x-1)-(bt2(e)-bt2(x-1));
				ret[y]=min(ret[y],ret[e]+goleft+goright);
				//e->y->x
				goright=bt(y)-bt(e);
				goleft=bt(y)-bt(x-1)-(bt2(y)-bt2(e-1));
				ret[x]=min(ret[x],ret[e]+goleft+goright);
			}
			
		}
		FORR(e,ev[i+1]) bt2.add(e,-1);
	}
	
	ll mi=1LL<<60;
	FORR(e,ev[V.size()-1]) mi=min(mi,ret[e]);
	cout<<mi<<endl;
	
}

まとめ

こういう問題、解が1ずれるのが怖い。