いものやま。

雑多な知識の寄せ集め

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) の値を出力するプログラムを書いてください。

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

自分の解答

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

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

 {
\begin{align}
F(n) &= \lfloor \log_{10} n^n \rfloor + 1\\
&= \lfloor n \log_{10} n \rfloor + 1
\end{align}
}

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

 {
m = \lfloor n \log_{10} n \rfloor + 1
}

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

 {
m - 1 \le n \log_{10} n < m
}

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

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

  1. 最初に  n = 1 とする。
  2. 以下を繰り返す:
    •  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. 以下を繰り返す:
    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 の数式がおかしくなるので、シンタックス・ハイライトなし

解説のコードと比べると、最初に上限を探しにいってるので、その分、ちょっとややこしいかも。

今日はここまで!