解説 yukicoder No.1235 ζ関数

yukicoder.me

別の用事でyukicoderを開いていたところ、唐突にコンテスト形式で問題公開されたので、解いてみました(´・ω・｀)

問題に提示されているリーマンゼータ関数をナイーブに実装すると、次のようになるはずです。

def f(n)
  a = 0
  (1..).each do |i|
    a += 1.0 / i**n
  end
  a
end

ここでaに足しこんでいっている1.0 / i**nはiが大きくなればなるほど、小さくなっていって、最終的には浮動小数点の精度では扱えなくなるほど小さくなり、実質的には0という状態になります。そうなると、aが変化しなくなってしまいます。この変化しなくなってしまったaが本問題の答えとなります。

出力が絶対誤差か相対誤差の小さい方が10⁶以下の時正解とみなされます。

と問題文にあるように、この問題ではそれほど高い精度は求められていません。浮動小数点の精度というのは、問題で求められている精度よりもずっと精度が高いので、「浮動小数点レベルで扱えなくなった時点で終了!」という雑な解法でもACできてしまうわけです。

わたしの提出したコードは次の通りです。

def f(n)
  a = 0
  (1..).each do |i|
    b = a + 1.0 / i**n
    return b if a == b
    a = b
  end
end

n = gets.to_i
p f(n)

yukicoder.me