Codeforces ECR #178 : F. Numbers and Strings

よくこういう問題思いつくな。
https://codeforces.com/contest/2104/problem/F

問題

非負整数xに対し、S(x)は以下のように定める。

• xとx+1を並べて書き、数字を昇順に並べ替えた値

整数Nが与えられる。
S(1),S(2),S(3),....,S(N)において何通りの異なる値が現れるか。

解法

xを、先頭から以下のようにa,b,cと3つのパートに分ける。

• cは9の連続
• bは9以外の1つの数字
• aは昇順に並べた数字(ただし先頭だけは0であってはならない)

この(a,b,c)は、S(x)を構成する最小の値である。
よって、前処理としてこのような(a,b,c)の構成を取る値を列挙しておけばよい。

vector<pair<string,int>> pat;
vector<int> ret;

int T;
ll N;

pair<string,int> num(string a) {
	int i;
	FOR(i,a.size()) if(a[i]!='0') {
		swap(a[i],a[0]);
		break;
	}
	int cur=atoi(a.c_str());
	string b=to_string(cur)+to_string(cur+1);
	sort(ALL(b));
	return {b,cur};
}

void dfs(string cur,int part) {
	if(*max_element(ALL(cur))>'0') {
		pat.push_back(num(cur));
	}
	if(cur.size()<9) {
		if(part) {
			dfs(cur+'9',1);
		}
		else {
			int i;
			FOR(i,10) {
				dfs(cur+(char)('0'+i),(char)('0'+i)<cur.back());
			}
		}
	}
		
	
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,10) {
		dfs(string(1,'0'+i),0);
	}
	
	sort(ALL(pat));
	FOR(i,pat.size()) {
		if(i==0||pat[i].first!=pat[i-1].first) ret.push_back(pat[i].second);
	}
	sort(ALL(ret));
	
	cin>>T;
	while(T--) {
		cin>>N;
		cout<<lower_bound(ALL(ret),N+1)-ret.begin()<<endl;
	}
}

まとめ

言われてしまえばそうなんだけど、最初から思いつくのは難しい。