CodeIQ「ロング・ロング・ストリング」問題を解いてみた。

CodeIQで出題された「ロング・ロング・ストリング」問題。

自分もRubyで解いたので、コードを公開してみる。

問題

問題は、以下のとおり：

自然数 $n$ に対して、関数 $F(n)$ を、 $n^n$ （ $n$ の $n$ 乗）を 10 進数で表したときの桁数と定義します。
例えば、 $5^5 = 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 \le m \le 10^{10})$ が与えられます。
標準出力に $G(m)$ の値を出力するプログラムを書いてください。

解説は以下で公開されている。

https://codeiq.jp/magazine/2016/03/38398/

自分の解答

自分の考えは、以下のとおり：

まず、 $F(n)$ は $n^n$ を10進数で表したときの桁数なので、次のように書くことが出来る：

なので、与えられた自然数 $m$ について、次の等式を満たす自然数 $n$ を見つければいいと分かる：

ただ、このままだと床関数が面倒なので、次のように変形：

あとはこの不等式を満たす自然数 $n$ を見つければいいんだけど、単に1から探していくのだと、効率が悪い。
ということで、こういうときの定番手法であるバイナリサーチを使うことにした。

バイナリサーチを使う場合、下限と上限が必要で、とりあえず下限は1と分かっているので、まずは下限を更新しつつ、上限を探すところから。

最初に $n = 1$ とする。
以下を繰り返す：
- $n \log_{10} n \lt m - 1$ なら、 $n$ はまだ小さいので、下限を $n$ で更新し、 $n \leftarrow 2n$ とする。
- $m - 1 \le n \log_{10} n$ なら、 $n$ は十分大きいので、上限を $n$ とし、ループを抜ける。

ちょっと注意が必要なこととして、 $m - 1 \le n \log_{10} n$ のとき、同時に $n \log_{10} n \lt m$ が成り立っていたら、条件を満たす $n$ が見つかったことになるので、そこで検索自体が終了になる。

これで上限が見つかったら、あとは普通にバイナリサーチ。

以下を繰り返す：
1. $n$ を下限と上限の中間の値にする。（小数点以下は切り捨て）
2. $m -1 \le n \log_{10} n \lt m$ を満たしていたら、 $n$ を返す。
3. そうでない場合、以下のように下限/上限を更新：
  - $n \log_{10} n \lt m -1$ なら、下限を $n$ で更新する。
    ただし、下限と $n$ が等しかったら、-1を返す。
  - $m - 1 \le n \log_{10} n$ なら、上限を $n$ で更新する。

ちなみに、上限を更新するときに終了のチェックをしていないのは、上限が $n$ と等しくなることはありえないから。
というのも、上限が $n$ と等しくなり得るのは、（小数点以下を切り捨てることから）下限と上限が等しいときのみで、下限は常に $n \log_{10} n \lt m -1$ を満たすように更新しているので、 $m - 1 \le n \log_{10} n$ とはなり得ないから。

以上をコードに落とすと、以下の通り：

include Math

def g(m)
  n = 1
  lower_bound = 1
  upper_bound = nil
  loop do
    value = n * log10(n.to_f)
    if (m - 1) <= value
      if value < m
        return n
      else
        upper_bound = n
        break
      end
    else
      lower_bound = n
      n *= 2
    end
  end

  loop do
    n = (upper_bound + lower_bound) / 2
    value = n * log10(n.to_f)

    if ((m - 1) <= value) && (value < m)
      return n
    end

    if value < (m - 1)
      if lower_bound == n
        return -1
      else
        lower_bound = n
      end
    else
      upper_bound = n
    end
  end
end

m = $stdin.gets.to_i
puts g(m)

※シンタックス・ハイライトすると、 $\TeX$ の数式がおかしくなるので、シンタックス・ハイライトなし