挑戦した問題

問題の要約

自然数 m（2 ≦ m ≦$ 10^{10} $）を受け取り、$ n^{n} $ の10進桁数がmとなるような自然数nを出力する。（そのようなnが存在しない場合は-1を出力する）

提出コード(Ruby(73))

n=m=gets.to_i
f=->{Math.log10(n)}
$".map{n=(m/f[]).to_i}
p n*f[]<m-1?-1:n

※問のテストケースに特化して短縮しているので、m=2,3,4,5,7,10,200などでバグります。（後述）

考え方

問の言い換え

$$ \begin{align} n^{n} が十進m桁 &\Leftrightarrow 10^{m - 1} \leq n^{n} < 10^{m} \\ &\Leftrightarrow m - 1 \leq n\log_{10}(n) < m \\ \end{align} $$

のように言い換えられますので、以下の２ステップで問題を解けば良さそうです。

$ f(x) = x\log_{10}(x) $ としたときの、$ f^{-1}(m) $ を求める。
$ m - 1 \leq f(\lfloor f^{-1}(m) \rfloor) < m $ を満たすかを調べる。
※満たさなかったら-1を出力、満たせば $ \lfloor f^{-1}(m) \rfloor $を出力。
※f(x)は問の領域（x≧2）であれば単調増加なので、 <m を満たさないのは$ f^{-1}(m) $が整数の場合のみです。

$ f^{-1}(m) $の求め方

上記方針では$ f^{-1}(m) $を求める必要がありますが、$ f(x) = x\log_{10}(x) $ の逆関数は簡単な形では表せません。そこで以下のような方法で近似値を求めることになります。

$ g(x)=x\log_{10}(x)-m $ とおき、$ g(x)=0 $の解をニュートン法で求める。
$ n = 10^{m/n} $ を満たすnを二分探索等で求める。
$ y=\frac{m}{\log_{10}(x)} $ と $ y=x $ のグラフの交点を漸化式で求める。（採用案）

今回はコードゴルフでの短縮化も狙っていたので、ちょっと書いてみて最も短そうな最後の方針を採りました。具体的には、以下のような数列を計算していきます。

$$ \begin{eqnarray} a_k = \begin{cases} m & ( k = 0 ) \\ \frac{ m }{ \log_{10}( a_{k -1} )} & ( k > 0 ) \end{cases} \end{eqnarray} $$

細かい証明は省きますが、$ y=\frac{m}{\log_{10}(x)} $ は殆どの領域で傾きの緩い（-1<傾き<0の）単調減少になっているので、下図のようにこの数列は収束していきます。

f:id:g_m_k:20160227133612p:plain

コーディング

ちゃんとした実装

上記を踏まえ、誤差が閾値以下となるまで数列の計算を繰返すアルゴリズムを実装すると以下のようになります。

require "bigdecimal"
def blog10(a)
    return BigMath.log(a, 50)/BigMath.log(10, 50)
end

s=m=gets.to_i
EPS = 1e-08   #閾値

begin
    prev_s,s = s,n/blog10(s)
end while (prev_s-s).abs > EPS
s=s.floor
p (m-1...m).cover?(s*blog10(s))?s:-1

大きなmで色々試したかったのでbigdecimalを使っていますが、設問の入力範囲であれば不要です。
「$ f^{-1}(m) $の求め方」の図の通り、数列は両側から収束していきます。ループが奇数回で終わると $ f^{-1}(m) $ が整数値だった場合（★）には、実際より1少ない値がs.floorで計算されてしまいます。ただし、★のような場合には$ n^{n} $の10進桁数がmとなるような自然数nが存在しないため、いずれにせよ-1を出力して正答となります。（少し手抜きですね）

ゴルフ版の実装（再掲）

n=m=gets.to_i
f=->{Math.log10(n)}
$".map{n=(m/f[]).to_i}
p n*f[]<m-1?-1:n

log10を何回も同じ引数で呼ぶため、lambda式（->記法）で短く宣言しています。
（メソッドの別名まわり詳しく無いので、もっと縮まるのかも）
$" はrequireで読み込まれたファイルの配列です。
環境によりますが、$".mapとすることで19回くらいループします。設問の範囲であればこれくらいで十分に収束します。（mが大きくなると、収束までのループ数はゆっくりとですが発散すると思います）
「問の言い換え」で示したステップ２の <m チェックを省いているため、$ f^{-1}(m) $ が整数だった場合（m=10,200,3000,...）には、-1を出力すべきところ解ありとして誤答します。
to_iを変なタイミングで行っているため、小さな値（m=2,3,4,5,7）では誤答となります。

GOTO M.

趣味のコーディングとか、勉強とか、読書とか

『ロング・ロング・ストリング』答案