競プロ典型90問 020 - Log Inequality（★3）コード解説

はじめに

最近かなり冷え込みますね。今年は12月に入っても割と暖かめだったのに今は皮膚を刺すような寒さです。今年はヒートテックを買おうかなあ…。

さて、今回も競プロ典型90問の★3問題から1問やっちゃいますよ！
今まで★3問題も前から解いていっていたのですが、実は018の「Statue of Chokudai」は飛ばしています。問題自体は解けたんですよ…。ただ、三角関数の問題なので、解説するのが少し面倒くさい…。誰も読んでない零細ブログだからさ…。なのでモチベーションが上がったときに三角関数の表とか用意して記事を書こうと思います。　　 　　 ささ、気を取り直して今回は「020 - Log Inequality」です！

競プロ典型90問

atcoder.jp

020 - Log Inequality

020 - Log Inequality

今回はめちゃくちゃシンプルな問題ですね。 出力もYesかNoの2通りしかありません。

まずは愚直に式のまま実装してみましょう。
pythonでlog(n)を計算するにはmathモジュールを用います。

import math
a, b, c = map(int, input().split(" "))

if math.log2(a) < b * math.log2(c):
    print("Yes")
else:
    print("No")

結論から言うとこのコードはWAでした。TLEでもなくシンプルに間違いです。

なぜなら、コンピュータは直接logを扱えないので、内部で近似した少数として扱っているからです。その値の多少のずれがプログラムをWAにしているのです。

正しい解法は以下になります。

a, b, c = map(int, input().split(" "))

if a < c**b:
    print("Yes")
else:
    print("No")

対数を理解している必要がありますが、`blogc = logc^b"が成り立ちます。そして対数関数は単調に増加する関数なので、xが増加すればyも増加することになります。つまりlogの引数だけで比べることが出来ます。

おわりに

今回は問題文もコードも短かったので精神衛生上良い問題でしたね！

修論で病んでるのでちょうどよい気晴らしになりました。

お疲れ様でした。