1019 Number Sequence
1019をid:keitanxkeitanが2分探索で解いていて,そんな問題だったかなぁとビックリした.自分のを見返してみたらやっぱり2分探索ではなかった.確かに2分探索でも解けるし実行時間は速いけど,こうやっても解けるよーっていう紹介.
概要
112123123412345... という文字列のi(1 <= i < 2^31)番目の文字を求めよ
考え方.
群数列みたいに考えて,1 12 123 1234 ...と分けて,x番目の群はいくつ文字を含むかを考える.x番目の群は少なくともx文字以上含みそうなので,x番目の群までの文字数の合計はx(x+1)/2より多そう.だから,xの範囲は x(x+1)/2 < 2^32 => x < 2^16ぐらいになりそう.多く見積もって2^16ぐらいまで調べればよいので,2分探索しなくても十分間に合う.
ソース内では,numcntがx番目の群の中の文字数を数える関数.含まれる群がわかったら,その群の文字列をstringstreamで生成してその文字列のi - sum(numcnt(1),numcnt(2),...,numcnt(x-1))番目の文字を出力している.
long long?
keitanはlong longを使っていたけど,確かに2^31番目あたりの文字を調べようとすると,それを含む群までの文字数の合計は2^31を超えてしまう.でも,足していくのではなく,引いていけば2^31を超えることはない.(ソース見てください)
数字->文字列変換
数字を文字にしたり,また長い文字列を単語に分ける時はstringstreamが便利.
stringstream ss; ss << 1 << 2 << 3; // ssの中身は"123" string s; ss >> s; // sは"123"
stringを使いたくないときはsprintfとか.
char s[10]; sprintf(s,"%d%d%d",1,2,3); //s は "123"
TopCoderでも"abc def ghi"みたいなstringが与えられて切り分けなきゃいけない時があるので,このときstringstreamを知ってると知っていないでは大違い.
ソース
int numcnt(int d){ int a = d; int ret = 0; int t = 1; int b = 1; while (d >= 10){ ret += t * 9 * b; d /= 10; t++; b*=10; } return ret + t * (a - b + 1); } int main(){ int T=nextInt(); while (T--){ int N=nextInt(); int i; for (i=1;N-numcnt(i) > 0;i++) N -= numcnt(i); stringstream ss; for (int j=1;j<=i;j++) ss << j; string str; ss >> str; cout << str[N-1] << endl; } }