前回の解答 & Rubyで整数の実数乗を概算する方法

はじめに

前回の続きです。

解答例

require 'socket'

def solve(y,z)
  ng = 0
  ok = 100_000_000_000_000_000_000
  while ok - ng > 1
    mid = (ok + ng) / 2
    if mid**y >= z
      ok = mid
    else
      ng = mid
    end
  end
  ok
end

def main
  sockin = TCPSocket.open('13.114.188.239', '23615')
  sockout = sockin

  puts response = sockin.gets
  puts response = sockin.gets

  10.times do
    puts response = sockin.gets
    puts response = sockin.gets
    x, y, z = response.gsub('^', '=').split('=')
    puts response = sockin.gets
    y = y.to_i
    z = z.to_i
    ans = solve(y,z)
    puts ans
    sockout.write("#{ans}\n")
  end

  loop do
    puts response = sockin.gets
    break if response.nil?
  end
end

main if $PROGRAM_NAME == __FILE__

x<=10^15なので、計算量は√xならば間に合います。単調性を利用して二分探索すれば解けます。

別解(整数の実数乗の計算)

よく考えるとこの問題ならば、実数乗を求めるだけなので、Pythonならばdecimalライブラリを使えば簡単に通りそうです。
RubyのBigDecimalライブラリを使ってみたところ、

require 'bigdecimal'

def solve(y,z)
  (BigDecimal(z)**(BigDecimal(1)/BigDecimal(y))).to_i
end

計算が遅すぎて1問目すら解くのに数分かかります。
とすると自分で高速な実数乗を実装するしかありません。
誤差は全く検証していない雑な実装のですが、テイラー展開A^B ＝ 1 + 1/1! * (lnA * B) + 1/2! * (lnA * B)^2 + ...の第100項までを使って、

def solve(y, z)
  d = Math.log(z) / y
  factrial = (1..100).inject([1]) do |arr, i|
    arr.push(arr.last * i)
  end
  100.times.inject(0) do |sum, i|
    sum += d**i * / factrial[i]
  end.round
end

とすれば解けました。

まとめ

答えが整数であることがわかっていたので、単調性を利用して二分探索でn乗根を求められました。
Rubyの算術関数は遅いものもあるので注意する必要がありますが、簡単な実装でも高速に必要な値を求められる場合もあります。
雑な計算ならばRubyで実装することも可能でしたが、やはり多倍長整数の計算はPythonを使うのが楽そうです。