Project Euler - Problem 230

まだ簡単なのが残ってた

Fibonacci Words

Problem 230 (日本語訳)

数字列 A, B に対して，シーケンス F_A,Bを { A, B, AB, BAB, ABBAB, ... } によって定める．つまり最初の二項 A, B を除いて，各項は前二項を連結させて作られる．

さらに，D_A,B(n) を F_A,B において初めて n 文字以上となる要素の先頭から n 番目の数字として定義する．


例:

A = 1415926535, B = 8979323846 としたときの D_A,B(35) を求める．

F_A,B の最初の数項を書き出すと，
1415926535
8979323846
14159265358979323846
897932384614159265358979323846
14159265358979323846897932384614159265358979323846

したがって，D_A,B(35) は 5 項目 35 番目の数字であり，それは 9 である．

A を π の小数点以下最初の 100 桁 :

14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679

B を次の 100 桁 :

82148086513282306647093844609550582231725359408128
48111745028410270193852110555964462294895493038196

としたとき，

$\sum_{n=0}^{17} 10^{n} \times D_{A,B} ((127 + 19n) \times 7^{n})$

の値はいくらか．

F_A,B の k 番目の要素を F_A,B,k とおき，その先頭から n 文字目を F_A,B,k(n) で定める．また F_A,B,k の長さを L_A,B,k とする．F_A,B,k の最初の数項を列挙すると，

F_A,B,0 = A
F_A,B,1 = B
F_A,B,2 = AB
F_A,B,3 = BAB
F_A,B,4 = ABBAB
F_A,B,5 = BABABBAB
F_A,B,6 = ABBABBABABBAB
F_A,B,7 = BABABBABABBABBABABBAB
F_A,B,8 = ABBABBABABBABBABABBABABBABBABABBAB

2 項前の列を赤，1 項前の列を青で色付けしてある．これをじっと眺めていると F_A,B,k(n) について次のことがわかる(わかってください)．

• n ≦ L_A,B,k-2 なら F_A,B,k(n) = F_A,B,k-2(n)
• n > L_A,B,k-2 なら F_A,B,k(n) = F_A,B,k-1(n - L_A,B,k-2)

これにより F_A,B,k(n) は最終的になんらかの i ≦ L_A,B,0 ( = L_A,B,1 ) を用いて， F_A,B,0(i) または F_A,B,1(i) の形で書ける．

また，n ≦ L_A,B,0 ( = L_A,B,1 ) であれば，

• F_A,B,k(n) = F_A,B,0(n) ( k : 偶数 )
• F_A,B,k(n) = F_A,B,1(n) ( k : 奇数 )

が成り立つ．これはシーケンス F_A,B の先頭のみに着目したとき A, B, A, B, A, B, … となっていることから従う．

これらを利用して D_A,B(n) を求めるコードは以下．

/* L : L_{A,B,k} を格納した配列*/
char D(string A, string B, lint n, lint* L) {

    /* L[k-1] < n ≦ L[k] となる k を見つける */
    lint k = 1;
    while ( L[k] < n ) k++;

    /* n が文字列 A, B の長さ以下になるまで */
    while ( L[0] < n ) {
        
        if ( L[k - 2] < n ) {
            n = n - L[k - 2];
            k--;
        }
        else
            k -= 2;
    }

    if ( k % 2 == 0 )   // k が偶数
        return A[n - 1];
    else                // k が奇数
        return B[n - 1];
}

最後にコード全体です．10 ミリ秒以下.

#include <string>
#include <iostream>
#include <time.h>

#define LEN 100
#define SIZE 80

using namespace std;
typedef long long int lint;

lint L[SIZE];

lint ipow(lint x, lint n)
{
    lint i, ret = 1;
    for (i = 0; i < n; i++)
        ret *= x;
    return ret;
}

lint f(lint n) {
    return ipow(7, n) * (19 * n + 127);
}

char D(string A, string B, lint n, lint* L) {

    lint k = 1;
    while (L[k] < n) k++;

    while (L[0] < n) {
        if (L[k - 2] < n) {
            n = n - L[k - 2];
            k--;
        }
        else
            k -= 2;
    }

    if (k % 2 == 0) return A[n - 1];
    else          return B[n - 1];
}

void PE0230() {

    string A("1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679");
    string B("8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196");

    L[0] = L[1] = LEN;
    for (lint i = 2; i < SIZE; i++)
        L[i] = L[i - 1] + L[i - 2];

    for (lint i = 17; i >= 0; i--)
        cout << D(A, B, f(i), L);
    cout << endl;
}

int main()
{

    clock_t start, end;
    start = clock();

    PE0230();

    end = clock();
    printf("%d msec.\n", end - start);

    return 0;
}

おまけ