読者です 読者をやめる 読者になる 読者になる

methaneのブログ

このブログに乗せているサンプルコードはすべてNYSLです。

PKU1019番

program

http://d.hatena.ne.jp/Ozy/20060510#p1
http://d.hatena.ne.jp/Ozy/20060512#p1
昨日に続き、PKUにチャレンジ。現在23:44。問題を読んでから4分経過。上でid:Ozyさんが解を出してるけど、それは見てない。
昨日はある程度考えてからまとめて書き、を繰り返していたが、今回は書きながら考えてみる。

1サイクルの長さ(文字数)を並べてみる。

1  :1
2  :12
...
9  :123456789
11 :12345678910
13 :1234567891011

[1-99]のときどうなるか。考えてみよう

桁数1 : 1-9        9文字
桁数2 : 10-99      90文字
桁数3 : 100-999    900文字

・・・見えて来たな。1*9 + 2*99 が[1-99]の文字数だ。
[1-N]の文字数は・・・数列の計算ってもうセンス無くしたよ。5年以上やってないからなぁ。clip(n,max)という関数があるとすると、

   charcount(N) := 1*clip(N,9) + 2*clip(N-9,90) + 3*clip(N-99,900) + ...

で表せるけれど、もっとスマートな式があるだろ・・・ま、いいか。

ここで24:00。やっぱ文章書きながらだと遅ぇ。こっからアルコール入る。

[1,12,123,1...,N]の文字数を考えてみる。
charcount(1) + charcount(2) + charcount(3) + ... + charcount(N)

あぁ、メンドくせぇ。別にきれいな数式作る必要ねぇじゃん。テキトーにやっちゃえ。

int positionedNum(int M) {
   int base = 1, baseLen = 1; // baseは1,10,100 baseLenは1,2,3
   unsigned int charsum = 0, nextsum; // Mに近づいていく値.
   unsigned int N; // 上で言ってたN
   int nlen = 0;   // Nの長さ.

   for (N=1;;++N) {
      if (N >= base*10) {
         baseLen ++;
         base *= 10;
      }
      nlen += baseLen;
      nextsum = charsum + nlen;
      if (nextsum < M) {
         sum = nextsum;
      }
      else {
         // 答は近い.
         // ここでなんかする.
         return なんか;
      }
   }
}

ここで24:25。うわ、ホント時間かかりすぎ。しかも、今回は文章じゃなくてプログラムで時間喰ってるのがイタイ。さて、「ここでなんかする」はどうしよう?
24:36。意識がもうろうとしてた。「なんかする」方法は思いついた。Mが2^32くらいの数値になっても、Nは2^17位にしかならない。普通に前から足していける桁数だ。でも、せっかく手前で似たことやってるんだから、そっちでテーブル作っちゃえ。

int positionedNum(int M) {
   int base = 1, baseLen = 1; // baseは1,10,100 baseLenは1,2,3
   unsigned int charsum = 0, nextsum; // Mに近づいていく値.
   unsigned int N; // 上で言ってたN
   int nlen = 0;   // Nの長さ.
   char *buff = malloc(0x40000); //これだけあれば十分なはず.

   for (N=1;;++N) {
      int i,n;
      if (N >= base*10) {
         baseLen ++;
         base *= 10;
      }
      n = N;
      for (i=1;i<=nlen;++i) {
         buff[buffend+nlen-i] = n % 10;
         n /= 10;
      }
      nlen += baseLen;
      nextsum = charsum + nlen;
      if (nextsum < M) {
         sum = nextsum;
      }
      else {
         return buff[M - charsum];
      }
   }
   free(buff);
}

こんな感じ?数列を三角形に並べて、上から下にたどってるから、計算量はO(N^0.5)になってるハズ?バグが入ってる自信はあるけど。明日仕事だしもう寝る。現在24:50。

結論:数列の復習をしましょう。