競プロ典型90問をRustで解いていこう（最大公約数[ユークリッドの互除法]）4日目

2022-03-12

はじめに

今日、ダイニングテーブルを買いました。前々からニトリや無印良品、IKEAなどで探していたのですが大きすぎるのと、まともなやつを探そうとすると3万～5万ぐらいするのを気にかけていました。値段が張る割には、作りが雑だったり大きすぎたり、椅子がイマイチだったりとピンと来ませんでした。

地域密着型の家具屋って覗いてなかったなと思い訪ねました。やはり想像通り、値段は10万～20万、中には100万近く行くようなダイニングセットも売っていて「これは場違いな所に来たなぁ」と店内を眺めていました。そんな中、一際輝く、展示品に限り特別大特価という商品がありまして、定価10万超えのダイニングセットが43,200円でした。特に傷とかもなく、サイズ感や質感が良かったので買っちゃいました。

当初は、予算3万5000円ぐらいで探していたので少し赤字ですが良いものを買えたんじゃないかと嬉しくなっています。

送料＋組み立て手数料、そしてリビングが傷つかないように敷くマットも付けてくれるとのこと。更に、購入したときに店の人が話しくれたのですが、「これ昨日メーカーから買い付けて、そのまま店頭に置いたやつだからほとんど新品なんだよね」。

家具は安いのか、高いのか正直判断に困るのですが、個人的にはニトリやIKEA家具よりも質が良さそうに感じています。届くのが楽しみです。

機嫌が良いので今日の問題をサクッと解いていきす。

本日の問題

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

今日は上の記事から2問目である、この問題を解いていきます。 022 - Cubic Cake（★2）

022 - Cubic Cake（★2）

幅 A、奥行き B、高さ C の直方体の形をしたケーキがあるので、どの面に対してか平行に切って、すべてのピースを立方体にするには何回切ればよいか求めることになります。

立てた方針

とりあえず、絵に書き起こしてみました。

方針のイラスト

点線のように各辺を等倍になるように切っていくことになります。等倍になるということは、公約数を求めるのが良さそうだろうとなりました。そしてその中で、一番切る回数が少なくて済むのが最大公約数となります。

最大公約数を求めて、各辺の長さと最大公約数の割り算をした合計を求めます。（切った回数が欲しいため-3をすればいけそうです。）

ユークリッドの互除法

最大公約数を求めるのであれば、高校数学でやったユークリッドの互除法が使えそうです。 10年近く昔のことなのでやり方がですねごっそり抜け落ちてるんですねぇ。調べました。

ユークリッドの互除法の手順
Step1: x を y で割り、余り r を求める
Step2: y を r で割り、その余り r_1 を求める
Step3: r を r_1 で割り、その余り r_2 を求める
...
Final: 余りが 0 になったときの割る数が最大公約数

Rustでの回答例

ユークリッドの互除法を再帰関数で定義してあげまず。 A,Bの最大公約数と、B,Cの最大公約数を求めて更にその結果同士の最大公約数を求めます。これで下準備は完了となりますので、各辺を何回切るかの計算に入ります。各辺の値を、最大公約数で割ります。この手順によって、何個のブロックに分かれるかが求められます。切った回数は各辺のブロック数-1個であるため調整します。

use proconio::input;

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

fn main() {
    input! {
        a: usize,
        b: usize,
        c: usize,
    }

    let max = gcd(gcd(a, b), gcd(b, c));
    println!("{}", (a / max + b / max + c / max) - 3);
}