Course Planning for Lazy Students

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1032&lang=jp
University of Aizu, ACM-ICPC Japan Domestic Contest Warm Up I, 16 May, 2009

//簡易コード　TLE版
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main()
{
   int N,U,K;
   while(cin>>N>>U,N|U){
      pair<int, vector<int> > piv[N];
      int ans = INT_MAX;
      for(int i=0; i<N; i++){
         cin>>piv[i].first>>K;
         for(int j=0; j<K; j++){
            int a; cin>>a; piv[i].second.push_back(a);
         }
      }
      for(int i=1; i<(1<<N); i++){
         int cnt = 0;
         int sum = 0;
         int tmp = 0;
         for(int j=0; (1<<j)<=i; j++){
            if( i&(1<<j) ){
               tmp++;
               if( tmp>ans )break;
               int k;
               for(k=0; k<piv[j].second.size(); k++)
                  if( !(i&(1<<piv[j].second[k])) )break;
               if( k==piv[j].second.size() ){
                  sum += piv[j].first; cnt++;
               }
            }
         }
         if( tmp==cnt && sum>=U && ans>cnt){
            ans = cnt;
         }
      }
      printf("%d\n",ans);
   }
   return 0;
}

組み合わせを列挙後、条件を満たしてるかのチェックをするアルゴリズム。
AOJだと、8秒ぐらいかかってTLE。答えはたぶん合ってる。
N<=20なので、ビットを使った組み合わせで綺麗に書ける。
まぁ、だめなんだけどｗ

//何故がAcceptもらったよくわからないコード。
#include <iostream>
#include <vector>
#include <climits>
#include <cstring>
using namespace std;

int N,U,C,K;
int ans;
pair<int, vector<int> > pivv[32];

void dfs(int now, int nowcost, int cnt, int next)
{
   if( ans<cnt )return;
   if( nowcost>=U ){ ans = cnt; return; }
   for(int i=next; i<N; i++){
      if( !(now&(1<<i)) ){
         int j;
         for(j=0; j<pivv[i].second.size(); j++)
            if( !(now&(1<<pivv[i].second[j])) )break;
         if( j==pivv[i].second.size() ){
            dfs(now|(1<<i), nowcost+pivv[i].first, cnt+1, i+1);
         }
      }
   }
   return;
}

int main()
{
   while(cin>>N>>U, N|U){
      pair<int, vector<int> > piv[N];
      ans = INT_MAX;
      for(int i=0; i<N; i++){
         cin>>piv[i].first>>K;
         for(int j=0; j<K; j++){
            int a; cin>>a;
            piv[i].second.push_back(a);
         }
      }
      
      // sort
      pair<int, vector<int> > tmp[N],pivtmp[N];
      vector<int> cv;
      int check[N];
      memset(check,0,sizeof(check));
      for(int i=0; i<N; i++)pivtmp[i]=piv[i];
      
      for(int i=0; i<N; i++){
         int pos=-1,tmin=N+1;
         for(int j=0; j<N; j++){
            int k;
            int c = 0;
            int n = pivtmp[j].second.size();
            
            for(k=0; k<n; k++){
               int l;
               for(l=0; l<i; l++)
                  if( cv[l]==pivtmp[j].second[k] )break;
               if( l<i || l==0 )c++;
            }
            
            if( c==n && tmin>n && !check[j]){
               pos = j; tmin = n;
            }
         }

         for(int j=0; j<N; j++){
            if( check[j] )continue;
            for(int l=0; l<pivtmp[j].second.size(); l++){
               if( pivtmp[j].second[l]==pos )
                  piv[j].second[l] = i;
            }
         }
         tmp[i] = piv[pos];
         check[pos] = 1;
         cv.push_back(pos);
      }

      for(int i=0; i<N; i++)pivv[i] = tmp[i];
      dfs(0,0,0,0);
      printf("%d\n",ans);
   }
   return 0;
}

解法は変にソート後、dfs+枝切り。
ソートの優先順位は、
・必修科目がない科目の集合
・↑の集合を用いて受講できる科目の集合
・↑の集合を用いて受講でき(ry

みたいな流れでソートさせても、組み合わせを探索したら
データセットによっては処理が終わらない、と思う。
AOJの判定データはよくない。
バグありのコードでもAcceptもらうことがある。
バグが発生するケースを自分で考えられない奴が文句言うな＞＜

鬱だにゃ。