hinamelプログラミングメモ

競技プログラミング・ゲーム制作の備忘録

ABC118 C Monsters Battle Royale 解説

問題文

atcoder.jp

・数列が与えられる。

・2つの数を選び、片方の数からもう片方の数の分引くという操作を繰り返す。

1つだけ1以上、他は0以下になるまで操作を繰り返すものとするとき、残った1つの値の最小値はいくつになるか求める。

ACコード

atcoder.jp

解説

まずこの問題を見て同じ数を何度も引くという操作を繰り返しているので、除算や商に関係があるものを使う可能性を考えておく。その上で色々なケースを考えてみる…

たとえば {2,4}のとき、4から2を引く⇒2から2を引く操作により{2,0}、つまり2が最小。

{2,4,6},{2,4,6,8}…でも同様にやることで最小の値は2になる。全ての数がnの倍数の時の最小の値はnになると考えられる。

では{2,3,4}のときはどうなるだろうか。この場合3から2を引くことで1が最小になる。

{2,4,5}や{2,4,5,7}などでも同様のことがいえる。

このようにいろいろな場合を考えたり、入出力例の内容から推測したりすることで、答えは数列の数全てについての最大公約数になることに気付く。よってそれを実装すればよい。ユークリッドの互除法を用いる。

 

解いた感想

体感難易度:☆2

最大公約数になることに気付けるかどうかの問題だった。入出力例と操作を見て法則に気付けるようになる訓練を重ねていきたい。