0

AtCoder の以下の問題 (ABC248-B) について、ループを回して不等式を満たす最小の整数 i を求めることでACになりました。

a*k^n≧bを満たす最小の非負整数nを求めよ。(a,b,kは自然数。k≧2)

それとは別に、直接、上の不等式を解くという方法も考えられます。
それでやってみたのが以下のコードなのですが、一つだけWAになりました。原因がわかりません。

a,b,k=gets.chomp.split(" ").to_a.map(&:to_i)
puts Math::log((b/a.to_f),k).ceil

1 件の回答 1

1

AtCoderのテストケースは以下の場所で公開されています。
https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0

WAになるテストケースを見てみると、以下のような入力となっています。

1 536870912 2

こちらの正しい出力は29ですが、ご提示のコードだと30が出力されます。

計算過程を追ってみると、Math::log((b/a.to_f),k)の結果が間違っていることが分かります。
5368709122 ** 29なので、Math::log(536870912.0,2) = 29.0となるべきなのに、実際に計算してみると誤差が入って29.000000000000004になってしまいます。こちらを切り上げて、30という誤った結果となっています。

浮動小数点数は誤差が入る可能性があるため、誤差が許容できない状況で使うのは避けるべきです。
特に、競技プログラムでは、このような誤差は狙い撃ちされます。
ケース名が「04_hack_log_01.txt」となっていることからも、logを使うとWAになるようにあえて追加されたテストケースであることは明白です。

1
  • ご回答ありがとうございました。 誤差が原因ではないかとは思ってはいたのですが、意図的に誤差が生じるテストケースが作られているんですね。 それから、テストケースが公開されているとも知りませんでした。ご教示ありがとうございます。 7月15日 9:42

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。