Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2399-e198d693
この記事にトラックバックする(FC2ブログユーザー)

SRM561 DIV1 EASY/DIV2 MEDIUM - ICPCBalloons (この記事を編集する[管理者用])

Source

TopCoder SRM561 DIV1 EASY (250pt)
TopCoder SRM561 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

ACM/ICPCのために風船を準備する.
手持ちの風船が与えられる.手持ちの風船の色は50種類以下.
各色の風船の数 (100以下),その風船のサイズが与えられる.
風船のサイズはMとLの2種類のみで,同じ色の風船は全部同じサイズ.
ACM/ICPCはK個 (15以下) の問題から成る.
各問題iに対して,同じサイズで同じ色の風船をA[i]個 (100以下) 用意しなければいけない.
違う問題には,違う色の風船を割り当てないといけない.
風船は自由に色を塗り替えることができる.
色を塗り替える風船の数の最小値を求める問題.不可能ならそれを指摘する.

解法

各問題に対して,使う風船のサイズを全部試す.
後は,A[i]の大きい方から,greedyに手持ちの中から多い風船を割りあてて行けば良い.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000000

class ICPCBalloons {
public:
int minRepaintings(vector <int> Count, string Size, vector <int> in) {
  int i, j, k, n;
  int sum;
  int A[100], A_size, A_sum, A_ed;
  int B[100], B_size, B_sum, B_ed;
  int res = INF, tmp;

  A_size = B_size = 0;
  rep(i,Size.size()){
    if(Size[i]=='M') A[A_size++] = Count[i];
    else             B[B_size++] = Count[i];
  }

  n = in.size();
  while(A_size < n) A[A_size++] = 0;
  while(B_size < n) B[B_size++] = 0;
  
  sort(A, A+A_size);
  sort(B, B+B_size);
  sort(in.begin(), in.end());

  A_sum = B_sum = 0;
  rep(i,A_size) A_sum += A[i];
  rep(i,B_size) B_sum += B[i];

  rep(k,1<<n){
    tmp = 0; A_ed = A_size-1; B_ed = B_size-1;
    
    sum = 0;
    for(i=n-1;i>=0;i--) if(k&1<<i){
      sum += in[i];
      if(in[i] > A[A_ed]) tmp += in[i] - A[A_ed];
      A_ed--;
    }
    if(sum > A_sum) continue;
    
    sum = 0;
    for(i=n-1;i>=0;i--) if(!(k&1<<i)){
      sum += in[i];
      if(in[i] > B[B_ed]) tmp += in[i] - B[B_ed];
      B_ed--;
    }
    if(sum > B_sum) continue;

    if(res > tmp) res = tmp;
  }

  if(res == INF) res = -1;

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2399-e198d693
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。