kojingharangの日記

Codeforces Round #129 Div1 A - Little Elephant and Interval

22:48 |

• 整数 A, B が与えられる。A≦X≦B な整数 X で、X を10進表記したときに最初と最後の桁が同じものの個数を求める問題。
• 1≦A, B≦10^18

• 1～x の範囲で条件にあうものの個数を計算する f(x) を書いて f(B) - f(A-1) すればよさげ
• 1桁ずつ見ていけばいいのでは
• x が N 桁として N-1 桁以下のものは [1-9]???[1-9] の形なので簡単そう
• N 桁のやつは最上位が x のやつ（これに大ハマリ）とそれ未満のやつに分けるかも
• naive なリファレンスを書いて一致を確認するがどうにも合わない

• 気づいたら90分...
• リファレンスと高速版で 10000 まで一致してることを確認してるので提出後の精神状態は良好
• Accepted
• 上位陣は5分くらいの模様。簡潔なのが多いなぁ

ll ff(ll d) {
	if(d==0) return 0;
	if(d==1) return 1;
	ll ans=1;
	REP(i, d-2) ans*=10;
	return ans;
}

ll ref(ll v) {
	ll co=0;
	for(int i=1;i<=v;i++) {
		ll msd=i;
		while(msd/10>0) {msd/=10;}
		if(msd==i%10) co++;
	}
	return co;
}

ll f(ll v) {
	if(v<10) return ref(v);
	if(v==0) return 0;
	ll msd=v, co=0;
	while(msd/10>0) {msd/=10;co++;}
	ll msdd=msd;
	REP(i, co) msd*=10;
	ll t=v, di=0;
	while(t>0) {t/=10;di++;}
	ll X = 0;
	int xok=0;
	{
		ll mm = (v-msd)/10;
		while(msd+(mm*10+msdd) > v && mm > 0) {
			mm--;
		}
		X = msd+(mm*10+msdd);
		if(X<=v) xok = 1;
	}
	ll vv= xok ? (X-msd)/10 +1 : 0;
	ll lower=0;
	REP(i, di) lower += 9*ff(i);
	ll ans= vv+(msdd-1)*ff(di)+lower;
	return ans;
}

int main() {
	//REP(i, 10000) {
	//	ll ra=ref(i);
	//	ll fa=f(i);
	//	if(ra!=fa) {cout<<"ERR"<<i<<" "<<ra<<" "<<fa<<endl;return 0;}
	//}
	
	ll L,R;
	while(cin>>L>>R) {
		cout<<f(R)-f(L-1)<<endl;
	}
	
	return 0;
}

ツイートする