CodeIQ：「ロング・ロング・ストリング」問題

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ロング・ロング・ストリング」問題（CodeIQ）を参照してください。

問題の概要

問題を引用します。

自然数 n に対して、関数 F(n) を、nn（n の n 乗）を 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 ≦ 10¹⁰）が与えられます。
標準出力に G(m) の値を出力するプログラムを書いてください。

私のプログラム

Pythonで解答しています。

#!/usr/local/bin/python3

import fileinput
import math

'''
	mの値からnの桁を確定する
	※先回のコードは桁数を求める処理が間違っていた
	※常に10桁になるので結果として正しい値が得られたが無駄な処理をしている
'''
def getRank(m):
	r = 0
	for i in range(1,11):
		if (10**i) * i > m:
			r = i
			break
	return r

'''
	mの値と桁からnの値を確定する。
	ここで求まるnはn**n<mを満たす最大のnであるが、問題のG(m)の解として正しい値とは限らない。
	例えばm=7の場合n=7を返すが7**7は6桁しかない。
'''
def fixValue(m,rank):
	ret = 0

	# 上の桁から値を確定する
	for i in range(rank-1, -1, -1):
		r = 10**i	# 値を確定する桁

		for j in range(10, 0, -1):
			v = j*r
			if (ret+v) > 0 and (ret+v) * math.log10(ret+v) <= m:
				ret += v
				break

	return ret

'''
	fixValue()でもとめたnを検算する。
	要件を満たさない場合は-1を返す。
'''
def check(n,m):
	if math.ceil(n*math.log10(n)) != m:
		return -1
	return n

'''
	問題の関数
'''
def G(m):
	r = getRank(m)
	n = fixValue(m, r)
	return check(n,m)

if __name__ == "__main__":
	for line in fileinput.input():
		if not line.strip():
			continue

		m = int(line.strip())
		print(G(m))

解説

この問題は問題の読解に時間がかかりました。わかりやすく言い直すと次のようになるでしょうか？
数字の桁（2以上）が与えられます。f(n)=log(nⁿ)がその桁数になるnを求めなさい。
なお、上記のlog()も以降のlog()も常用対数です。

考え方

桁数が無茶苦茶大きいので対数の考え方を使います。天文学の世界では距離などの精度がどの程度正しいかを言うのに「桁はあっている」などということがありますが、常用対数を利用してnの桁を確定します。
nが何桁か確定したらnの各桁の値を決定して答えを求めます。

getRank()

入力値mからnの桁を求めます。
問題のG(m)はG(m)=log(nⁿ)の整数部分です。これを変形すると、
G(m) = n×log(n) （の整数部分）
となります。そしてlog(n)の部分がnの桁数になります。
forでnの桁数を1〜10まで回し、mを超えない最大の値を求めることでnの桁数を求めます。

fixValue()

getRank()で決まった桁と入力値mからnを求めます。
やっていることは簡単で上の桁から順番に10,9,8,7,…,2,1とやって、nを近似してゆきます。nの近似値をn'とすると、1桁ごとにn'×log(n')を計算します。この値がmを超えたら大きすぎたことになるので、n'×log(n')がmを超えない最大のn'が決まったら1つ下の桁をに移って同じことを繰り返し精度を上げてゆきます。そして1の位まで決まったらn=n'となります。

check()

ただし、fixValue()で決まった値が正しいとは限りません。なので検算します。これはF(n)でF(n)はnⁿの桁数なのでn×log(n)の整数部分です。これがmと等しくなければ-1、等しければnを返します。

雑感

この問題はすでに出題者の解答例が出ています。私のコードでもそこそこ早いです（私のローカルマシンでm=999999999の時に上記のコードで0.035秒くらいで終わります）が解答例のように二分法で探索する解答例の方が効率が良いですし、実装もエレガントです。