裏紙

ほぼ競プロ、たまに日記

ABC 029 - D: 1

・問題分
D: 1 - AtCoder Beginner Contest 029 | AtCoder

・アイデア
各桁ごとに数字の現れ方に規則性があるから桁ごとに注目して数え上げればいいじゃんってのには気づいたけどそれをうまく実装できなかった。解説スライド(http://www.slideshare.net/chokudai/abc029)を見て、「なるほどこういう感じで行けばloopに落とし込めるなあ」と感心した。
その日に実装したかったけどなんかうまくできなかったので今日やり直してみた。最近ABC全完が目標となっている私にとっては残念。


・実装

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;

int main(){
	int n;
	cin >> n;
	
	long ans=0;
	
	for(int i=0; i<10; ++i){
		long cycle = pow(10,i+1); //i桁目の1サイクル
		
		long r = (n+1)%cycle;
		if(r==0) r=cycle;
		
		ans += (n/cycle)*(cycle/10);
		if(r<=cycle/10){}
		else if(r<=cycle/5) ans+=r-cycle/10;
		else ans+=cycle/10;
		
		//printf("cycle = %ld, r = %ld\nnow :%ld\n",cycle,r, ans);
	}	
	
	printf("%ld\n", ans);
}