競プロ典型90問をRustで解いていこう（LCM/オーバーフロー）7日目

2022-03-23

はじめに

メダリストの5巻が発売されました。フィギュアスケートものの漫画なのですが、熱いです。

こういうのは大変失礼な話ではあるのですが、絵柄はどこか佐渡川準先生を彷彿とさせます。目元の書き方とか。

話の内容は正統派スポ根です。才能はあるけど自身もなく埋もれていた主人公が、熱血コーチとオリンピックを目指すというストーリーです。登場人物皆が、競技に掛ける思いがあって、それをぶつけ合うのが非常に熱いわけです。

みんな買おうな。 Kindleで１巻は無料だよ。ほら早く読もう。

| |

本日の問題

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

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

033 - Not Too Bright（★2） 038 - Large LCM（★3）

を解いていこうと思います。

033 - Not Too Bright（★2）

LEDが縦と横に敷き詰められている。2✕2の4つの空間で1つだけ光るようにしたとき最大何個光らせるかという問題です。

立てた方針

各空間の左上を光らせたら良さそうです。敷き詰めているので、縦、横2つに1つ光らせているので縦/2 ✕ 横/2 で求めることができそうです。端っこの場合でもLEDを光らせれるので、そのケースにおいては、掛けるもとの値に＋１して計算すれば良いです。

Rustでの回答例

縦か横が1のときには素直に掛け算します。それ以外のときは隅っこを考慮したケースにあたるので、＋１して計算します。

use proconio::input;

fn main() {
    input! {
        h: usize,
        w: usize,
    }

    if h == 1 || w == 1 {
        println!("{}", h * w);
    } else {
        println!("{}", ((h + 1) / 2) * ((w + 1) / 2));
    }
}

038 - Large LCM（★3）

今日はもう一問解いときましょう。以前、最小公約数を求めましたが、今度は最小公倍数を求める問題です。

立てた方針

公式を素直に実装します。「２つの自然数の積はその最小公倍数と最大公約数の積に等しくなる」というものがあります。式にするとこうなります。

$$ a_b = lcm_ gcd lcm = \frac{(a*b)}{gcd} $$

最小公約数は作ったものを使い回せば良いので、最大公約数を求める関数を上の式に当てはめます。

Rustでの回答例

あとは大きな値がオーバーフローしてしまうので、u128型で定義しておきます。ホントは規定値以上は計算しないようにするのが良いんでしょうが、u128で定義すれば桁数が足りるので…

10の18乗を超えるときはLargeを出力するとのことなので、if文で出力します。

use proconio::input;

fn gcd(x: u128, y: u128) -> u128 {
    if y == 0 {
        x
    } else {
        gcd(y, x % y)
    }
}

fn lcm(x: u128, y: u128) -> u128 {
    return (x * y) / gcd(y, x % y);
}

fn main() {
    input! {
        a: u128,
        b: u128,
    }
    let lcm = lcm(a, b);
    if lcm <= 1000000000000000000 {
        println!("{}", lcm);
    } else {
        println!("Large");
    }
}