Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【ARC054-B ムーアの法則】三分探索

B - ムーアの法則

問題

今の計算機の能力ではP時間かかるタスクがある。しかし、計算機の能力は1.5年で2倍ずつ上がっていく。最短で何時間後にタスクを終わらせることが出来るか?

方針

 f(x) = x + P / 2^{x/1.5}

は下に凸な関数なので三分探索で求めることが出来る。はっきり言ってそれだけの問題。AtCoderの参加者のレベルも1.5年で2倍のペースで上がっているため、そのうちABCのBで出されるようになるはず、というジョークが理解出来ない人はもうこのブログを読まなくていい。

微分して傾き0のところを二分探索で求めるという方針でもいけるかも知れないが、却ってややこしくなりそうなのと、三分探索は実装が簡単でサンプルと突き合わせれば間違いようがないのでそのまま解く。

上に凸でも解くことが出来る(正負逆転させてもいいし、比較のところを逆にしてもどちらでもよい)

実装

pow関数は、数値のメソッドとして定義もされているが、実際にコードを書くと、コンパイルエラーで鬱陶しいことになったり、レシーバの部分にかっこが増えて読みにくくなって誤りの元だと思うので、f64::xxxの形で使うのが良いと思った。

fn solve() {
    input! {
        P: f64,
    }
    let f = |x: f64| { x + P/f64::powf(2.0, x/1.5) };
    let mut lb = 0.0;
    let mut ub = P;
    while ub > lb + 0.00000001 {
        let t1 = (2.0*lb+ub)/3.0;
        let f1 = f(t1);
        let t2 = (lb+2.0*ub)/3.0;
        let f2 = f(t2);
        if f1 <= f2 {
            ub = t2;
        } else {
            lb = t1;
        } 
    }
    println!("{}", f(lb));
}