ARC094 C : Same Integers(300)
作成日：2018.09.04
最終更新日：2018.09.04
問題概要
整数$A,B,C$に対し、操作1「2つ選んでそれぞれ$1$増やす」、操作2「1つ選んで$2$増やす」のいずれかを繰り返し行い、3つの整数をすべて等しくする。
この時に必要な操作の最小回数を求めよ。
制約
$0 \leq A,B,C \leq 50$
考え方
操作によって整数は小さくならないから、最終的には$max(A,B,C)$($=M$とする)以上になる。
また同じ2つの整数を選んで操作1を2回行うのは、それぞれの整数に対して操作2を1回ずつ行うのと同じである。
よって$M$を超えないように各整数に対して操作2を行っても良い。
この時各整数は$M$または$M-1$のいずれかであり、少なくとも1つの整数は$M$である。
$M-1$が0個の時はそのままで良い。
$M-1$が1個ある時はその整数を選んで操作2をし、残りの2つの整数を選んで操作1をすれば$M+1$で等しくなる。
この時はすべてを$M$にすることはできないのでこれが最適である。
また$M-1$が2個ある時はその2つの整数を選んで操作1を1回すれば$M$で等しくなる。
以上により答えを求めることができた。
ソースコード
マクロ等はこちら
int A,B,C;
int main(){
cin >> A >> B >> C;
if(A < B) swap(A,B);
if(A < C) swap(A,C);
int ans = (A-B)/2 + (A-C)/2;
if((A-B)&1){
if((A-C)&1) ++ans;
else ans += 2;
} else if((A-C)&1) ans += 2;
cout << ans << endl;
return 0;
}解法まとめ
3つの整数の中で最大のものを超える直前まで各整数に対し操作2を行う。この回数は$O(1)$で求められる。(5-7行)
この操作の後、最大のものに等しくない数の個数が1個の時はさらに操作を2回、2個の時はさらに操作を1回行う必要がある。(8-11行)
答えはこれらの操作の回数の合計である。