読者です 読者をやめる 読者になる 読者になる

CodeIQ 挑戦の記録 : 「ロング・ロング・ストリング」問題

CodeIQというサイトで問題に挑戦した記録です。

codeiq.jp

問題文を要約すると下記の通り

  • 自然数{n}に対して関数{F(n)}{{n}^{n}}を10進数で表した時の桁数と定義する。
  • 2以上の自然数{m}に対して関数{F(n)=m}となる{n}の値を{G(m)}と定義する。
    そのような{n}が存在しない時は{G(m)=-1}と定義する。
  • 標準入力から{ m \ (2 \leq m \leq {10}^{10})}が与えられる。
  • {G(m)}を出力する。

方針

題意より{F(n)=m} は次の数式で表す事ができる。
\begin{align} floor( \log_{10} {n}^{n} ) + 1 =m \end{align}

これを変形し、
\begin{align} m-1 \leq \log_{10} {n}^{n} < m
\end{align} これを{n}について解けば{O(1)}のコードが書けるが、この数式を解く能力は自分には無いのであっさり諦める。
上式を
\begin{align} floor( n \log_{10} n)+1=m \end{align}
と変形し{F(n)=m}となる{n}を探索する事にする。
但し、線形探索{O(N)}では、入力の最大{{10}^{10}}に対して1秒の時間制限をクリアする事は出来無い。
そこで、二分探索{O(\log N)}を自前で実装する事とする。

実装

提出したコードは下記の通り
(実際は下記をワンライナーにしたもの。134byte)

では、


Sponsored Link