Hatena::Grouptopcoder

hotokuの日記@topcoder部 このページをアンテナに追加 RSSフィード

 | 

2012-10-13

SRM 557

| 15:54

midに時間掛かり過ぎ。殆ど、時間ギリまで使ってしまった。アルゴリズムは単純なので、こういうのをスムーズに提出出来るようにならないとなかなか上に行けない。


easy

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class GreatFairyWar{
public:
  int minHP(vector <int> dps, vector <int> hp){
    int ret=0;
    size_t n = dps.size();
    for(size_t i = 0; i < n; ++i){
      for(size_t j = i; j < n; ++j){
	ret+=dps[j]*hp[i];
      }
    }
    return ret;
  }



};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


mid IncubatorEasy

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;

size_t n;
bool magical[100], proc[100], visit[100];
vector<string> graph;


class IncubatorEasy{
public:
  void dfs(int pos, bool is_proc);
  int count_valid(int flag);
  int maxMagicalGirls(vector <string> love);
};

void IncubatorEasy::dfs(int pos, bool is_proc){
  if(is_proc){
    proc[pos]=true;
  }
  if(visit[pos]) return;
  visit[pos]=true;
  for(size_t i = 0; i < n; ++i){
    if(graph[pos][i]=='Y'){
      dfs(i, true);
    }
  }
}
int IncubatorEasy::count_valid(int flag){
  fill(proc, proc+n, false);
  fill(visit, visit+n, false);
  for(size_t i = 0; i < n; ++i){
    magical[i] = flag & 1<<i;
    if(magical[i]) dfs(i, false);
  }
  int ret=0;
  for(size_t i = 0; i < n; ++i){
    if(magical[i] && !proc[i]){
      ret++;
    }
  }
  // copy(magical, magical+n, ostream_iterator<bool>(cout, ","));
  // cout << ":" << ret << endl;
  return ret;
}
int IncubatorEasy::maxMagicalGirls(vector <string> love){
  n = love.size();
  graph = love;
  int flag=0;
  int ret=0;
  while(flag < 1<<n){
    ret=max(ret, count_valid(flag++));
  }
  return ret;
}
 |