TopCoder SRM 786 : Div1 Easy SwapTheString

久々にMediumがどうにもならなかった…。
https://community.topcoder.com/stat?c=problem_statement&pm=16133&rd=17989

問題

ある文字列Sが与えられる。
距離Kにある2文字をswapすることを任意回数行えるとする。
ただし、swap後は辞書順で大きな文字になっていなければならない。

任意の順でswapするとき、swapを最大何回行えるか。

解法

Sから、i文字目から初めてK文字ごとに文字を抜き出したものを考える。
T(i) := (S[i+nK]を連結したもの)
この各T[i]で、隣接要素をswapすることを考える。

結局各文字において、手前にある自身より辞書順で小さな文字の数だけswap可能なので、それを数え上げればよい。

vector<ll> A;
class SwapTheString {
	public:
	long long findNumberOfSwaps(string P, int A0, int X, int Y, int N, int K) {
		A.clear();
		A.push_back(A0);
		int i,j,x;
		for(i=1;i<N;i++) A.push_back((A.back()*X+Y)%1812447359);
		for(i=P.size();i<N;i++) P.push_back(A[i]%26+'a');
		ll ret=0;
		FOR(i,K) {
			string T;
			int C[26]={};
			for(j=i;j<N;j+=K) {
				
				FOR(x,P[j]-'a') ret+=C[x];
				C[P[j]-'a']++;
			}
		}
		return ret;
		
	}
}

まとめ

これはえらく楽だったな。