1019 Number Sequence

1019をid:keitanxkeitanが２分探索で解いていて，そんな問題だったかなぁとビックリした．自分のを見返してみたらやっぱり２分探索ではなかった．確かに２分探索でも解けるし実行時間は速いけど，こうやっても解けるよーっていう紹介．

概要

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ぐらいまで調べればよいので，２分探索しなくても十分間に合う．

ソース内では，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;
  }
}