CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「ロング・ロング・ストリング」問題解説

2016.03.11 Category:CodeIQ問題解説・リーダーボード Tag: ,

  • 11
  • このエントリーをはてなブックマークに追加

「数学の問題をプログラミングで解こう!」シリーズ。

巨大な数の桁数に関する問題です。
数学のとある概念を使うと、非常に解きやすくなります。みなさんはうまく解けましたか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックして下さい!
by CodeIQ運営事務局

問題のおさらい

自然数 n に対して、関数 F(n) を、nnnn 乗)を 10 進数で表したときの桁数と定義します。
例えば、55 = 3125 ですので、F(5) = 4 です。同様に、F(20) = 27 です。

さらに、2 以上の自然数 m に対して、F(n) = m となる n の値を G(m) と定義します。
もしそのような n が存在しない場合は、G(m) = -1 と定義します。

例えば G(4) = 5、G(27) = 20 です。同様に、G(7) = -1、G(101) = 57、G(11111) = 3173 となることが確かめられます。

標準入力から、自然数 m(2 ≦ m ≦ 1010)が与えられます。
標準出力に G(m) の値を出力するプログラムを書いてください。

方針

非常に長い桁数の数字に関する問題です。

まず、nn 乗の値そのものを計算するアプローチがうまくいかないことは、多くの方が気づかれたのではと思います。本問で扱う数は、桁数が最大で 1010 桁もある巨大な数です。通常のプログラミング言語の数値型の変数では、精度が不十分だったり、莫大なメモリ量を要したりして、うまく扱うことができません。

そこで役に立つのは、常用対数 の考え方です。常用対数とは、10 を底とする対数(log)のことです。巨大な数のおおよその値を表すための概念で、まさに今回のケースにうってつけです。

さらに、常用対数には、10進数の桁数との深い関連性があります。自然数 x に対して log x の整数部分に 1 を足すと、x の桁数に等しくなるのです。

参考:常用対数(Wikipedia)

したがって、n に対する nn 乗の桁数は、次のコードで求められます。

// nのn乗の桁数
long long NumOfDigitsOfNToTheN(long long n) {
    return 1 + (long long)(n * log10((double)n));
}

さて、この関数を使って、この値が m に等しくなるような n を探索するコードを書けばよさそうです。しかし、n を 1 から始めて 1 ずつ増やしていく次のようなコードはうまくいきません。m の上限が 1010 もあり、頭から探索する方法では時間がかかり過ぎてしまうためです。

// 時間がかかり過ぎてしまうコード
#include <iostream>
#include <math.h>
using namespace std;

long long NumOfDigitsOfNToTheN(long long n) {
    return 1 + (long long)(n * log10((double)n));
}

int main() {
    long long m = 100, d;
    cin >> m;
    for (long long n = 1;; n++) {
        d = NumOfDigitsOfNToTheN(n);
        if (d == m) { // 発見!
            cout << n << endl;
            break;
        }
        else if (d > m) { // 存在せず
            cout << -1 << endl;
            break;
        }
    }
    return 0;
}

二分法で高速探索!

そこで本問では二分法というテクニックを用いて、高速に答えを求めましょう。二分法がどういうものかについては下記をご覧下さい。

参考:二分法(Wikipedia)

上記コードの NumOfDigitsOfNToTheN 関数は単調増加です。区間上限を十分大きく(1011 など)、区間下限を十分小さく(1 など)すれば、初期条件としては適切です。あとは、ループの中で、n を区間下限と区間下限の中点としたときの NumOfDigitsOfNToTheN 関数の値を求め、それが目的の m より大きいか小さいかで区間の狭め方を決定しましょう。目的の m に等しければ、そのときの n が求めるべき答えです。

ひとつ注意点です。本問では、一般的な二分法とは異なり、n は連続値ではなく離散的な整数値をとります。このため、解が存在しない場合があり、そうしたケースをうまく検出してループを脱出しなければなりません。一例ですが、区間下限と区間下限の中点が前回と同じであればループを抜けるというやり方が可能です。

コード例は以下です(C++)。

#include <iostream>
#include <math.h>
using namespace std;

long long NumOfDigitsOfNToTheN(long long n) {
    return 1 + (long long)(n * log10((double)n));
}

int main() {
    long long m = 100, d;
    long long left = 1, right = 100000000000LL, mid;
    cin >> m;
    while (true) {
        if (mid == (left + right) / 2) {
            cout << -1 << endl;
            break;
        }
        mid = (left + right) / 2;
        d = NumOfDigitsOfNToTheN(mid);
        if (d == m) {
            cout << mid << endl;
            break;
        }
        else if (d < m) left = mid;
        else right = mid;
    }
    return 0;
}

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)こちらもぜひチェックして下さい。

CodeIQ「ロング・ロング・ストリング」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
Kawazoeさんの次の問題にご期待ください!

  • 11
  • このエントリーをはてなブックマークに追加

■関連記事

【謎解きプログラム】座標の移動【Matrix】解答と解説... 【謎解きプログラム】座標の移動【Matrix】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以内に...
数学の問題をプログラミングで解こう!「ストレート・ラインズ」問題解説... 問題のおさらい 2 以上の自然数 n に対し、n×n の格子状に並んだ点を考えます。 これらの点のうちちょうど 2 個の点を通る直線の数を F(n) と定義します。 例えば F(2)=6 です。題意を満たす直線は以下の 6 通りです。 また、F(3)=12 です。題意を満たす直線は以下の...
【謎解きプログラム】この処理は?【コードを読もう】解答と解説... 【謎解きプログラム】この処理は?【コードを読もう】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以...
数学の問題をプログラミングで解こう!「ループ・トラッキング」問題解説... 問題のおさらい 自然数 n に対し、関数 Fn(x) を次のように定義します(floor():床関数)。 例えば n=10, x=1 のとき、F10(1) = floor(4×1×9÷10) = 3 です。 さて、整数 k(0 ≦ k ≦ n)に対して、関数 Fn による変換を繰り返し行い...
【謎解きプログラム】どんな結果になる?【アロー関数】解答と解説... 【謎解きプログラム】どんな結果になる?【アロー関数】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
数学の問題をプログラミングで解こう!「カウント・スリー」問題解説... 問題のおさらい 自然数を 1 から順に書き並べていきます。 このとき、3 の数字が現れる回数を数えます。 自然数 n に対し、ちょうど n 個目の 3 の数字が現れたときに書いている数を F(n) と定義します。 例えば F(10)=35 です。 下の通り、10 個目の 3 は、35 を書いて...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ