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行)
 答えはこれらの操作の回数の合計である。

ARC094の他の問題 D E F

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告