–2025/04/14
今日久しぶり快晴です。早速洗濯をして、家事をすませました。
今日、Atcoderの093回目を挑戦しようと思います。
やっぱりC問題に少し時間が掛かりそうです。
ABCという三つの数字に、以下の操作を何回行うと、すべて同じ数字になるという問題です。
①三つの中に、二つを選んで、それぞれ+1
②三つの中に、一つを選んで、それを+2
具体例を見てみると、
例えば、2,5,4の三つの数字に、どのように操作したら、同じ数字になるか、
考察すると、以下の流れになります。
もう一つの例を見てみる、
例えば、2,3,6という三つの数字に、どのように操作したら、同じになるか、
以上の２例の処理の共通点を洗い出すと、
①昇順して、一つ目と二つ目の数字をそれぞれ+1、
②上記の操作を二つ目と三つ目の数字が同じになるまで、繰り返す
③以上の処理が終えると、二種類の結果が考えられる、
a)三つの数字が同じになる この場合、処理が終了となる。
b)一つ目の数字が他の二つ数字より小さくなる、この場合、一つ目の数字を+2の操作を行い、その他の数字と同じか或は大きくなるまで繰り返す
④一つ目の数字がその他の数字より大きくなる場合、二つ目と三つ目の数字をそれぞれ+1、三つの数字が同じになるまで繰り返す
このようなロジックを組んで、正解になりました。
これは一体どんなアルゴリズムでしょうか？
解説を読んで、貪欲法というものになります。
以下のサイトを参考して、読み合わせて、いいのかなと思います。
貪欲なアルゴリズム（greedy）入門 | アルゴリズムロジック
crossorigin="anonymous">