競プロ典型90問をRustで解いていこう(誤差)12日目

2022-05-14

はじめに

PS5がEDIONで購入できたので非常にウキウキではあるのですが、ソフトがない。 PS4のときに買ったSEKIROをやるか、Youtube、Amazon Prime再生機としての役目しかないような状態です。

DEATH STRANDINGを買ったのでやろうとしたんですが、50GB近くのデータ移行してからの起動とかでやりたいときにできないのは非常にもどかしいですね。

PS3ぐらいの時期から思ってましたが、ゲームをやりたいだけなのに起動するまでに初期セットアップとか アカウントを作って連携しろとか、インストールするとか、アップデートが必要とか 遊ぶまでのハードル高くない? PS2とかソフト入れるBIOS起動する、ゲームで遊ぶだったじゃん。 ファミコンとかはソフト挿して即起動だったじゃん。あれぐらいの気概を見せて欲しい。

とまぁ、何はともあれ次世代ゲーム機なのでかなり楽しみです。

あと楽しみで言えば、ブルーピリオドの最新刊が今月発売ということで予約しておきました。

楽しみが多いのはいいことです。

本日の問題

競プロ典型90問をRustで解いていこう(準備)0日目

今日は上の記事から12問目を解いていきます。

020 - Log Inequality(★3) を解いていこうと思います。

020 - Log Inequality(★3)

$$\log_2a < b\log_2c$$

が成り立つかどうかを求める問題です。 そのまま計算しようとすると、数値計算上の誤差によって本来であれば異なる値になるところが 同じ値になってしまうようなケースがあります。 i128型で計算したら普通に通るのですが…

Rustでの回答例

log計算が不要になるように式変形を行います。

$$\log_2a < b\log_2c$$ $$\log_2a < \log_cb$$ $$a < cb$$

a,b,cは全て1以上の整数なので計算しても全て整数となります。 これを満たすコードをRustで書けばよいです。

use num_traits::pow;
use proconio::input;

fn main() {
    input! {
        a : i128,
        b : usize,
        c : i128,
    }
    let bc = pow(c, b);
    if a < bc {
        println!("Yes");
    } else {
        println!("No");
    }
}

実行結果

まとめ

実装はライブラリがあるので簡単なんだけど、式変形とかパッと思いつかないと解けない問題もあるのね。