人工知能と競プロやってくブログ

深層学習・機械学習・AI・atcoder・競技プログラミングについて調べてやってみたことをまとめるブログです

AtCoder Beginner Contest 118 [ C - Monsters Battle Royale ]をPythonで解く。最大公約数(GCD, greatest common divisor)を求める問題(300点、🟫茶diff)

問題

atcoder.jp

解法

とにかく入力例とか問題の内容読むと「これ約数の問題っぽくない!?」と悟れという問題のよう。
最大公約数がモンスターのHPの最小値になるので、これを求めればよい。

3つ以上のパラメータの最大公約数の求め方が実装例(Python3.8系)。
math.gcdはPython3.9以降では、素直に3つ以上要素が入ったリストを渡せば計算できるようだ。

実装

参考

blog.hamayanhamayan.com

flytech.work