mayoko’s diary

プロコンとかいろいろ。

AOJ 1295 Cubist Artwork

問題

Cubist Artwork | Aizu Online Judge

箱を並べる。これを前から見ると D 列のキューブが X1, X2, ..., XD 個並んでいるように見え, 横から見ると W 列のキューブが Y1, Y2, ..., YW 個並んでいるように見える。
これを満たすようなキューブの並べ方のうち, 必要なキューブの数が最小のものは, いくつのキューブを必要とするか(条件を満たす並べ方が存在することは保証されている)。

解法

サンプルにいろいろな例が書いてあるので, 自分で書いて実験してみましょう。すると, 以下のような解法でいけることがわかります。

  • Xi と Yj が一致していたら, (i, j) 座標に Xi を置けば OK
  • そうでない場合は, いい感じのところ(Xi の値が一番大きいところにカモフラージュするようにする)に置けば, 少なくとも Xi (1 <= i <= D) の部分は合う
  • 後は Yi を埋める
bool done[22];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int W, D;
    while (cin >> W >> D) {
    	if (W==0 && D==0) break;
    	vi X(W), Y(D);
    	for (int i = 0; i < W; i++)
    		cin >> X[i];
    	for (int i = 0; i < D; i++)
    		cin >> Y[i];
    	memset(done, false, sizeof(done));
    	int ans = 0;
    	for (int i = 0; i < W; i++) {
    		ans += X[i];
    		for (int j = 0; j < D; j++) {
    			if (!done[j] && X[i] == Y[j]) {
    				done[j] = true;
    				break;
    			}
    		}
    	}
    	for (int i = 0; i < D; i++) {
    		if (!done[i]) ans += Y[i];
    	}
    	cout << ans << endl;
    }
    return 0;
}