TopCoderOpen 2020 Round2B : Easy FixedNumberOfDigits

今回も見送ったけどレート的にはよかったのかな…。
https://community.topcoder.com/stat?c=problem_statement&pm=16283&rd=18074

問題

公差が1～10の範囲である等差数列が与えられる。
この数列を初項から書いていったとき、計N個数字を書いた時点で止めたとする。
最後に書いた(数字ではなく)数値は何か。

解法

どの値の頭何桁を書くか求めればよい。
まず、公差が10以下なので要素毎の桁数は高々1しか差がない。

等差数列中、これからd桁の整数がk個続くなら、N≦d*kなら今からfloow((N-1)/d)+1個目の値を頭((N-1)%d+1)桁出力しよう。
N＞d*kなら、N-=(d*k)として(d+1)桁目に続く。

ll p10[20];



class FixedNumberOfDigits {
	public:
	long long sum(int start, int step, long long numberOfDigits) {
		p10[0]=1;
		int i;
		int len=1;
		FOR(i,18) {
			p10[i+1]=p10[i]*10;
			if(start>=p10[i+1]) len=i+2;
		}
		ll cur=start;
		while(1) {
			ll nex=p10[len];
			ll num=(nex-cur+step-1)/step;
			if(num*len<numberOfDigits) {
				numberOfDigits-=num*len;
				cur+=num*step;
				len++;
				continue;
			}
			numberOfDigits--;
			ll s=numberOfDigits/len;
			cur+=s*step;
			numberOfDigits-=s*len;
			return cur/p10[len-1-numberOfDigits];
		}
		return -1;
}

まとめ

こちらは典型問題かな。