TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

leading zerosにならない回文の数の$K$番目を求める．番目は$0$-indexed.

$1$桁の回文は$1, 2, 3, 4, 5, 6, 7, 8, 9$の$9$個．
$2$桁の回文は$11, 22, 33, 44, 55, 66, 77, 88, 99$の$9$個．
$3$桁の回文は$2$桁の回文の真ん中に$0 \sim 9$までの$10$個を入れれば良いので$90$個．
$4$桁の回文は$3$桁の回文を作る時に挿入した数字を並べるだけなので，同じ$90$個．
…
といったように，$1, 2$桁以外は奇数の場合はその前の桁の個数$\times 10$，偶数の場合はその前の桁と同じ個数となる．なので，まず始めに$K$番目の回文数は何桁の数字かを出す．これは今書いたルールどおりに桁の区間を$[l, r)$として探索する．

何桁かが分かったら次に，その桁の中で何番目かを求める．これを仮に$N$番目とする．例えば，5桁の時の回文数を半分だけ見て，最初が$100$から始まるためそれを引いてみると
$$ 10001 \to 100 \to 0 \\ 10101 \to 101 \to 1\\ 10201 \to 102 \to 2\\ … \\ 10901 \to 109 \to 9\\ 11011 \to 110 \to 10 $$ $N$番目が出てくる．つまり桁数が決まったら$K$番目の数字は，$(\frac{桁数}{2} - 1) ^{10} + (K - l)$の数字を更に反転して連結したものとなる．(偶数の時はそのまま反転，奇数の時は最後の数字はいらない)

Code

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

class IntegerPalindrome {
  public:
  long long findByIndex(int K) {
      ll ret = 1;
      int l = 0, r = 9;

      if(l <= K && K < r) {
          return K + 1;
      }

      ret = 9;
      l = r;
      r += ret;

      if(l <= K && K < r) {
          return (K - l + 1) * 10 + (K - l + 1);
      }

      int cnt = 3, keta = 1;
      while(true) {
          if(cnt & 1) {
              keta++;
              ret *= 10;
          }
          l = r;
          r += ret;

          if(l <= K && K < r) break;
          cnt++;
      }

      ll t = 1;
      rep(i, keta-1) t *= 10;
      ll res = K - l + t;

      stringstream ss;
      ss << res;
      string s = ss.str();

      stringstream ss2;
      ss2 << s;
      if(cnt & 1) {
          for(int i = s.size() - 2; i >= 0; i--) ss2 << s[i];
      } else {
          reverse(s.begin(), s.end());
          ss2 << s;
      }

      s = ss2.str();

      ll ans = 0;
      t = 1;

      for(int i = s.size()-1; i >= 0; i--) {
          ans += (int)(s[i] - '0') * t;
          t *= 10;
      }

      return ans;
  }
};

ry0u_ydのblog

SRM302 D1M IntegerPalindrome

TopCoder Statistics - Problem Statement

Code