問題 E - ファーストアクセプタンス

http://atcoder.jp/problem/detail/29
169(45)分で正解

貪欲かなー、と頭のなかで操作するけどうまくいかない
最大サイズが1000なので、1000^2のDPでも間に合う
自分が解く時間ではなく、誰かが解く時間で昇順ソートさせて、
その問題を取るか取らないか、記録するのは経過した時間
dp[FACを取った個数] = 現在まで使った時間の最小値

int dp[1010];
pair<int,int> prob[1010];

bool cmp(const pair<int,int>& a, const pair<int,int>& b){
  return a.second < b.second;
}

int main(){
  int n;
  int a,b;
  while(cin>>n){
   
    rep(i,n){
      scanf("%d%d",&a,&b);
      prob[i].first = a;
      prob[i].second = b;
    }
    
    sort(prob,prob+n,cmp);

    int ret = 0;
    rep(i,n+1)dp[i] = INT_MAX;
    dp[0] = 0;
    rep(i,n){
      int t = prob[i].first;
      int li = prob[i].second;
      if( t>li ) continue;
      for(int j=i; j>=0; j--){
	if( dp[j]==INT_MAX )continue;
	if( dp[j]+t > li ) continue;
	if( dp[j+1] > dp[j]+t ){
	  dp[j+1] = dp[j]+t;
	  ret = max(ret, j+1);
	}
      }
    }
    printf("%d\n",ret);
  }
  return 0;
}

2011/5/17 03:xx 追記
上記は計算量O(n^2)のDPでしたが、工夫すれば計算量O(nlogn)で解ける（ってiwi先生のブログに書いてた)らしいので解いてみた。
まず、他の誰かが解く時間でソートする（同じ
次に、優先度付きキューのデータ構造（降順)を利用して、貪欲に処理していきます
問題iにかかる時間 Ai
問題iが誰かに解かれる時間 Bi
自分が今までかけた時間の和 time

• Bi >= time + Ai　のとき、優先度付きキューに Ai を追加し、timeにAiを加算
• そうではなく、
  • 優先度付きキューが空じゃないとき、
  • 優先度付きキューの一番上の要素taと、Aiを比較し、ta > Aiのとき、
    • 要素taを優先度付きキューから削除し、Aiを優先度付きキューに追加、timeからtaを引いてAiを加算する

全ての問題に対して処理が終わったときの、優先度付きキューのサイズが最大で解ける問題数になります

int dp[1010];
pair<int,int> prob[1010];

bool cmp(const pair<int,int>& a, const pair<int,int>& b){
  return a.second < b.second;
}

int main(){
  int n;
  int a,b;
  while(cin>>n){
   
    rep(i,n){
      scanf("%d%d",&a,&b);
      prob[i].first = a;
      prob[i].second = b;
    }
    
    sort(prob,prob+n,cmp);

    priority_queue<pair<int,int> > q;
    int ret = 0;
    int time = 0;
    rep(i,n){
      a = prob[i].first;
      b = prob[i].second;

      if( b < time + a ){
	if( !q.empty() ){
	  int ta = q.top().first;
	  if( ta > a ){
	    q.pop();
	    time = time - ta + a;
	    q.push(prob[i]);
	  }
	}
      }else{
	q.push(prob[i]);
	time += a;
	ret++;
      }
    }

    printf("%d\n",ret);
    
  }
  return 0;
}