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。
結論：数列の復習をしましょう。
