AOJ-1149 : ケーキカット - kengo92iの日記

概要

長方形のケーキを，縦横にカットして切り分けていきます．切り分けたケーキには識別番号が付けられ，識別番号は，1回カットが行われるたびに付け替えられます．最終的に切り分けたそれぞれのケーキの面積を昇順に出力します．

解法

ケーキのカットする位置は左上から，縦横の長さがマイナスになるまで交互に引き続けます．値を引いた回数が偶数か奇数で，縦横のカットを判断する．(mod使った方が良かったみたいです)

識別番号の付け方は，構造体ソートで解決できます．識別番号の付ける条件が以下のように説明されています．

先に生まれたピースほど識別番号が小さい．

1回のカットで生まれる二つのピースについては，（上から見た）面積の小さい方が識別番号も小さい．二つのピースの面積が同じになる場合には，どちらの識別番号が小さいと考えても構わない（どちらにしても最終的な答えには影響しない）．

なので，構造体で以下のように定義しています．

bool operator<(const cake &c) const {
	if(turn != c.turn) { return turn < c.turn; }
	return area < c.area;
}

最後に，それぞれのピースの面積を取り出して，昇順ソートすれば終わりです．

ソースコード

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1149

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

struct cake {
	int w, d, area, turn;
	cake(int w_, int d_, int turn_)
		: w(w_), d(d_), area(w_*d_), turn(turn_) {}
	bool operator<(const cake &c) const {
		if(turn != c.turn) { return turn < c.turn; }
		return area < c.area;
	}
};

vector<cake> cakes;

int main() {
	int n, w, d;
	while(cin >> n >> w >> d, w) {
		int turn=0;
		cakes.clear();
		cakes.push_back(cake(w, d, turn));
		int p, s;
		rep(i, n) {
			++turn;
			cin >> p >> s; p--;
			cake piece = cakes[p];
			cakes.erase(cakes.begin() + p);
			
			int k=1, diff=s;
			for(; diff > 0; ++k) {
				diff -= (k % 2) ? piece.w : piece.d;
			}
			
			diff *= -1;
			if(k % 2) { //縦分割
				int d1 = piece.d - diff;
				int d2 = diff;
				cakes.push_back(cake(piece.w, d1, turn));	
				cakes.push_back(cake(piece.w, d2, turn));	
			} 
			else { //横分割
				int w1 = piece.w - diff;
				int w2 = diff;
				cakes.push_back(cake(w1, piece.d, turn));	
				cakes.push_back(cake(w2, piece.d, turn));	
			}

			sort(ALL(cakes));
		}

		vector<int> result;
		rep(i, cakes.size()) result.push_back(cakes[i].area);

		sort(ALL(result));
		rep(i, result.size()) {
			if(i != 0) cout << " ";
			cout << result[i];
		}
		cout << endl;
	}
	return 0;
}