2007年国内予選C問題（Cut the Cake）(2007/07/30(月) 01:10:47)

2007年国内予選C問題のCut the Cake（ケーキカット）をやってみました。

解法

1つ1つのピースを切られた順番、大きさ（縦・横）で管理する。
切られたピースは削除し、新たに２つ新しいピースを追加する。

ソートは、切られた順番にソートするless(<)オペレータと、小さいピース順にソートするgreater(>)オペレータを使用する。
各ソートはsort関数を使いたかったため、大小記号には関係ない。（ややこしいことするな！！）

ソース

（目標２５分以内）

#include <iostream>
#include <vector>
using namespace std;

typedef struct PIECE{
  int no;
  int w, d;
  bool operator < (const PIECE &p) const{
    return no < p.no || no == p.no && w * d < p.w * p.d;
  }
  bool operator > (const PIECE &p) const{
    return w * d < p.w * p.d;
  }
}PIECE;

int main(){
  int n, w, d;

  while(cin >> n >> w >> d, (n || w || d)){
    vector<PIECE> l;
    PIECE p = {-1, w, d};

    l.push_back(p);

    for(int i = 0; i < n; i++){
      int p, s, x = 0, y = 0;
      cin >> p >> s;

      vector<PIECE>::iterator iter = l.begin();
      for(int j = 1; j != p && iter != l.end(); j++, iter++);
      if(iter == l.end())cout << &quote;Error!!&quote; << endl;

      s %= l[p - 1].w * 2 + l[p - 1].d * 2;
      if(s < l[p - 1].w)x = s;
      else if(s < l[p - 1].w + l[p - 1].d)y = s - l[p - 1].w;
      else if(s < l[p - 1].w * 2 + l[p - 1].d)x = s - (l[p - 1].w + l[p - 1].d);
      else y = s - (l[p - 1].w * 2 + l[p - 1].d);

      if(x > 0){
        PIECE p1 = {i, x, (*iter).d};
        PIECE p2 = {i, (*iter).w - x, (*iter).d};
        l.erase(iter);
        l.push_back(p1);
        l.push_back(p2);
      }
      else{
        PIECE p1 = {i, (*iter).w, y};
        PIECE p2 = {i, (*iter).w, (*iter).d - y};
        l.erase(iter);
        l.push_back(p1);
        l.push_back(p2);
      }

      sort(l.begin(), l.end(), less<PIECE>());
    }
    sort(l.begin(), l.end(), greater<PIECE>());
    int i;
    for(i = 0; i < l.size() - 1; i++){
      cout << (l[i].w * l[i].d) << " ";
    }
    cout <<(l[i].w * l[i].d) << endl;
  }

  return 0;
}

参考

ACM/ICPC International Collegiate Programming Contest, Asia Regional Contest 2007, Tokyo, Japan