TopCoderOpen 2020 Round4 : Medium SortInversions

シンプルな設定。
https://community.topcoder.com/stat?c=problem_statement&pm=16406&rd=18191

問題

正整数Nが与えられる。
1～Nを、それぞれ文字列とみなしたときに昇順となるように並べたとする。
その数列の転倒数を求めよ。

解法

Nがd桁だとする。
まず、d未満の桁数における転倒数を求めよう。
x桁の数値Aがy桁(x＜y)の数値Bの前に配置されるのは、Bの先頭x桁がA未満の場合である。
これは10^(y-x)*(9*10^(x-1)-1)*(9*10^(x-1))/2とO(1)で求められる。

最後に、d未満の桁数の整数Mを総当たりしよう。
N以下のd桁の整数のうち、先頭|M|桁がM未満のものを列挙すれば、O(10^d)で解くことができる。
N=10^10の時だけTLEするので、そこは埋め込んでしまおう。

ll p10[12];

class SortInversions {
	public:
	long long count(int N) {
		int i;
		if(N==1000000000) return 45454542010101000LL;
		p10[0]=1;
		FOR(i,10) p10[i+1]=p10[i]*10;
		int d=0;
		while(N>=p10[d+1]) d++;
		d++;
		ll ret=0;
		int x,y;
		for(x=1;x<d;x++) for(y=x+1;y<d;y++) {
			ll a=0;
			a=p10[x]-p10[x-1]-1;
			a=a*(a+1)/2;
			ret+=a*p10[y-x];
		}
		
		int cd=0;
		for(int cur=1;cur<p10[d-1];cur++) {
			if(cur>=p10[cd]) cd++;
			ll v=min((ll)N,cur*p10[d-cd]-1);
			ret+=v-p10[d-1]+1;
		}
		return ret;
	}
}

まとめ

過去どこかで出てたっぽいね。