「ロング・ロング・ストリング」問題解答 ( CodeIQ )
はじめに
CodeIQというところでプログラミング問題「ロング・ロング・ストリング」に解答しましたので、ネタバレです。
(2016/3/15追記) CodeIQ Magazineの記事はこちらです。
(追記終わり)
問題
入力 m に対して、以下で定義される関数$G(m)$の値を出力する、という問題です。
- 整数$n$に対して、$n^n$の10進数での桁数を返す関数を$F(n)$とする。
- 整数$m $に対して、$F(n)=m $ となる n が存在する場合$G(m)=n$、存在しない場合 $G(m)=-1$とする。
なお、$2\le m \le 10^{10}$ なので、2番目の条件で n が複数存在することは考えなくても良いようになっています。
解説
提出版は次のRuby(103)でした。
※最初Ruby(100)でパスしたのですが、バグがあることに気付いて締め切り間際で再提出しました。
m=eval *$<
p (f=->d,u{u-d<2?-1:eval(%W(n f[n,u] f[d,n])[m<=>(Math.log10(n=u+d>>1)*n).floor+1])})[2,m+2]
一般に、正の整数 x の10進数としての桁数は$\lfloor \log_{10}x \rfloor+1$ で表すことができます。
そうすると、$F(n)=\lfloor n\log_{10}n\rfloor +1$ に対する $F(n)=m $の求解なので、 $F(n)$ が単調増加であることを考えると、解として可能性のある下限 3 と上限 $m+1$ の間の バイナリサーチで次のように Ruby(65) で組めるはずですが…
p (3..1+m=gets.to_i).bsearch{|x|m<=>(Math.log10(x)*x).to_i+1}||-1
しかし、CodeIQのRuby1.9.3ではbsearchが使えないので、ついカッとしてbsearchもどきを 組んでしまいました。文字数的には全然ですが。
Ruby2以降のbsearchと違って、閉区間ではなく開区間で範囲を指定し、eval を使った一種の遅延評価により、条件分岐ではなく配列の添え字アクセスによってバイナリサーチを実現しています。
最後に
実は桁数計算を$1+\lfloor\log_{10}x\rfloor$ではなくて$\lceil\log_{10}x\rceil$と勘違いしていました。もちろん殆どのケースではどちらでも同じ計算結果にはなるのですが…。エラー、ボーンヘッドですね。
(2016/03/11追記)
いつもの通り、togetterにまとめができました。バイナリサーチ以外にも、ニュートン法等の収束計算での方法があるようです。ご参考まで。
