blog.bouzuya.net

2022-03-17 アルゴリズムと数学 演習問題集 091, 092, 093 を解いた

アルゴリズムと数学 演習問題集 091 - How Many Ways? を解いた。

問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_br

N <= 100 から (a, b, c) の組み合わせを全探索しても 10^6 なので間に合う。素直に三重ループの中で a + b + c = X の判定をして個数を数えれば良い。

提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30187985


アルゴリズムと数学 演習問題集 092 - Beautiful Rectangle を解いた。

問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bs

N <= 10^12 なので縦と横の組み合わせを全探索では間に合わない。求めるのは H * W = N なので N の約数を列挙する。 N の約数は x * x <= N の範囲まで x を探索すればいいので \sqrt{N} になる。これは 10^6 なので間に合う。

1 から x * x <= N の範囲で x を順に調べて N % x == 0 なものについて x * 2 + (N / x) * 2 の最小値を求めれば良い。

提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30188078


アルゴリズムと数学 演習問題集 093 - Large LCM(★3) を解いた。

問題: https://atcoder.jp/contests/math-and-algorithm/tasks/typical90_al

競プロ典型 90 問の 38 日目と同じ問題だ (https://atcoder.jp/contests/typical90/tasks/typical90_al) 。

LCM(A, B) を求める。 10^18 を超える場合は Large と出力する。

LCM(A, B) = A * B / GCD(A, B)GCD(A, B) = if A == 0 then B else GCD(B, A % B)

オーバーフローに注意する必要がある。 A * B / GCD(A, B) とすると A * B の時点でオーバーフローしてしまう可能性がある。 A / GCD(A, B) * B としてなるべく値が小さくなるようにする。A / GCD(A, B)B の掛け算部分はこのままだとオーバーフローする可能性がある。 Rust の場合は checked_mul を使えばオーバーフローを検出できる。使わない場合は 10^18A で割ったものとの大小比較などをすれば判定できる。

提出: https://atcoder.jp/contests/math-and-algorithm/submissions/30188152


今日のコミット。