Good Bye 2021: E. Lexicographically Small Enough

良くもなく悪くもなくな回。
https://codeforces.com/contest/1616/problem/E

問題

N文字の2つの文字列S,Tが与えられる。
Sの隣接2文字のswapを繰り返し、Sを辞書順でTより小さくしたい。
最小何回swapが必要か。

解法

• (i-1)文字目までSとTを一致させて、i文字目でS[i]＜T[i]とする。

とするための最小swap回数を、iを総当たりしながら求めよう。

S[i]＜T[i]とするには、S[i]～S[N-1]の中でT[i]より小さい最寄のindexを求めるだけ。
問題は「(i-1)文字目までSとTを一致させて」の部分だが、これは文字種別ごとにBITなどでその文字があるindexの集合を管理させればできる。

int Q;
int N;
string S,T;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[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;}
	void add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,20> bit;
deque<int> C[26];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>N>>S>>T;
		
		FOR(i,26) {
			C[i].clear();
		}
		FOR(i,N+1) {
			bit.set(i,0);
		}
		FORR(c,S) c-='a';
		FORR(c,T) c-='a';
		FOR(i,N) {
			C[S[i]].push_back(i);
			bit.add(i,1);
		}
		ll cur=0;
		ll mi=1LL<<60;
		FOR(i,N) {
			x=T[i];
			FOR(j,x) {
				if(C[j].size()) {
					mi=min(mi,cur+bit(C[j][0])-1);
				}
			}
			if(C[x].empty()) break;
			cur+=bit(C[x][0])-1;
			bit.add(C[x][0],-1);
			C[x].pop_front();
		}
		if(mi==1LL<<60) mi=-1;
		cout<<mi<<endl;
		
	}
}

まとめ

方針はすぐ定まるけど、ちょっと実装が面倒くさいタイプの問題。