読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

UVa 102 - Ecological Bin Packing

UVa

UVa第二回目です。今回はBackGround読んでいません。

- 問題概要

3つの器に3色のビンがごっちゃになって入ってます。一つの器に一色のビンだけ入るようにしたいのですがビンを移動させる本数の合計を最小にしなければなりません。
出力はどの器にどの色を入れるかを'B''C''G'を使って表示する。
左の器に茶色、真ん中の器に緑、右の器に透明のビンを入れる時には"BGC"と表示する。
このとき、移動回数の最適解が複数存在するときには表示する文字列が辞書順で最小のものを採用する。

- 解法

全探索です。どの器にどの色のビンを入れるか決定するだけなのでパターン数は6しか存在しません。
最適解が複数存在するときは辞書順の最小のものを採用しなければならないのですが、辞書順の小さい順から計算をしていけばこの問題は解消できます。

- ソースコード

#include<iostream>
#include<algorithm>
#include<string>
#define rep(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define LL long long
using namespace std;
char color[3] = { 'B', 'C', 'G' };
int pt[6][3] = { { 0, 1, 2 }, { 0, 2, 1 }, { 1, 0, 2 }, { 1, 2, 0 }, { 2, 0, 1 }, { 2, 1, 0 } };
int num[3][3];
int main(void){
	while (cin >> num[0][0] >> num[0][2] >> num[0][1]
		>> num[1][0] >> num[1][2] >> num[1][1]
		>> num[2][0] >> num[2][2] >> num[2][1]
		){
		LL all_sum =  
			num[0][0] + num[1][0] + num[2][0]+
			num[0][1] + num[1][1] + num[2][1]+
			num[0][2] + num[1][2] + num[2][2] ;

		LL ans = 1 << 30;
		int p = 0;
		rep(i, 0, 6){//pattern_index
			LL sum = all_sum;
			rep(j, 0, 3){
				sum -= num[j][pt[i][j]];
			}
			if (ans > sum){
				ans = sum;
				p = i;
			}
		}
		cout << color[pt[p][0]] << color[pt[p][1]] << color[pt[p][2]] << " " << ans << endl;
	}
}