KUPC2015 : G - ケンドー

本番中に解ききれず。
http://kupc2015.contest.atcoder.jp/tasks/kupc2015_g

問題

N人で構成される２つのチームが対戦する。
両チーム並び順を決めると、互いに同じ順番に並んだ者同士が戦う。
両チームのメンバーの能力はA[i],B[i]であり、能力の低い方が負けである。

ここで、２つ目のチームの能力B[i]は昇順であることが分かっている。
１つ目のチームのメンバーの順番を、隣接するもの同士入れ替える、ということを繰り返し、１回も負けないようにしたい。
最小で何回メンバーの入れ替えを行えばよいか。

解法

Bの強い順に対戦相手を決めていく。
B[y]に負けないA[x]のうち、最も位置が後のものをB[y]と戦わせる、ということを順次繰り返していけば良い。
setとBITを用いて、B[y]に負けないA[x]の集合と、(初期状態で)x番の人間をy番まで移動するswap回数を求めていく。

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

BIT<int,20> bt;
int N;
int A[101010],B[101010];
vector<pair<int,int> > V;

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],i});
		bt.add(i,1);
	}
	FOR(i,N) cin>>B[i];
	sort(ALL(V));
	
	set<int> S;
	ll ret=0;
	x=N-1;
	for(i=N-1;i>=0;i--) {
		while(x>=0 && V[x].first>=B[i]) S.insert(V[x--].second);
		if(S.empty()) return _P("-1\n");
		y = *(--S.end());
		S.erase(y);
		ret += bt.total(N+1)-bt.total(y);
		bt.add(y,-1);
		
	}
	
	cout<<ret<<endl;
}

まとめ

本番弱い順に処理しようとしてえらい苦労してしまった。