yukicoder : No.968 引き算をして門松列（その３）

そういえば正月一発目はこれか。
https://yukicoder.me/problems/no/968

問題

3つの正整数A,B,Cが与えられる。
これらの整数に以下の処理を繰り返し行うことを考える。

• コストXでAとCをデクリメントできる。
• コストYでBとCをデクリメントできる。
• コストZでAとBをデクリメントできる。

最終的にA,B,Cが正整数でかつ門松列をなすようにするのに必要な最小コストを求めよ。

解法

「２つをデクリメントする」は「残り１つをインクリメントする」と相対的には同じ。
なので、4通りの並び順(B-A-C, B-C-A, A-C-B, C-A-B)を総当たりして、それぞれを実現する最小コストを求めよう。
ただし、それぞれの操作を実際に行うと、A,B,Cが０以下になるケースは除く。

int T;
ll A,B,C,X,Y,Z;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>A>>B>>C>>X>>Y>>Z;
		
		ll mi=1LL<<60;
		
		// B->C->A
		{
			ll TA=0;
			ll TC=max(A+1,C)-C;
			ll TB=max(C+TC+1,B)-B;
			if(A-TC-TB>0 && B-TA-TC>0 && C-TA-TB>0) mi=min(mi,TA*Y+TB*Z+TC*X);
		}
		// B->A->C
		{
			ll TC=0;
			ll TA=max(C+1,A)-A;
			ll TB=max(A+TA+1,B)-B;
			if(A-TC-TB>0 && B-TA-TC>0 && C-TA-TB>0) mi=min(mi,TA*Y+TB*Z+TC*X);
		}
		// C->A->B
		{
			ll TB=0;
			ll TA=max(B+1,A)-A;
			ll TC=max(A+TA+1,C)-C;
			if(A-TC-TB>0 && B-TA-TC>0 && C-TA-TB>0) mi=min(mi,TA*Y+TB*Z+TC*X);
		}
		// A->C->B
		{
			ll TB=0;
			ll TC=max(B+1,C)-C;
			ll TA=max(C+TC+1,A)-A;
			if(A-TC-TB>0 && B-TA-TC>0 && C-TA-TB>0) mi=min(mi,TA*Y+TB*Z+TC*X);
		}
		
		
		if(mi==1LL<<60) mi=-1;
		cout<<mi<<endl;
		
	}
}

まとめ

4問目が思いつけば後は簡単かな。