Hatena::Grouptopcoder

thorikawa@top coder

topcoder id: the_poly
 | 

2013-02-21

TopCoder - SRM571 Div1

18:21 | はてなブックマーク - TopCoder - SRM571 Div1 - thorikawa@top coder

グラフ強化月間の甲斐なく、500が解けなかった。後から考えると実装自体は大したことがない問題だったので悔しい。

さておき、REP(i,n) REP(j,n) {} みたいに{}なしでREPを連続させると、breakしたつもりでしてないミスが多いので、もうこの書き方はやめようと思う。

結果

AC/Opened/Unopened 1668-> 1636

250 FoxAndMp3

DFSするだけ。

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
typedef vector <int> vi;

int limit;

void solve(int s, vi& v) {
  int i;

  if (s > limit) return;

  v.push_back(s);
  if (v.size() >= 50) return;
  REP(i,10){
    int target = s*10+i;
    if (target > limit) break;
    solve(target, v);
    if (v.size() >= 50) return;
  }
  return;
}

class FoxAndMp3 {
public:
vector <string> playList(int n) {
  limit = n;
  int i;
  vi v;
  for(i=1; i<10; i++){
    solve(i, v);
    if (v.size() >= 50) break;
  }
  vector<string> w;
  REP(i,v.size()){
    char buf[256];
    sprintf(buf, "%d.mp3", v[i]);
    w.push_back(string(buf));
  }
  return w;
}
500 MagicMolecule

頂点数は50だが、頂点数の制約から、そこから減らせる数はmaxで16くらいなので、どれを減らしていくかでDFSすれば高々O(2^16)の計算量。しかし、このコードはなかなか綺麗だと思う(自我自賛)。

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)

int n;
vector<int> power;
vector<string> bond;

int solve(vector<int> flag){
  int i,j;
  // check if it satisfy the number condition
  int m = count(flag.begin(), flag.end(), 1);
  if (3*m < 2*n) return -1;
  
  // check if this is a clique
  bool isClique = true;
  REP(i,n) {
    REP(j,i) {
      if(flag[i] && flag[j] && bond[i][j] == 'N'){
        isClique = false;
        break;
      }
    }
    if (!isClique) break;
  }

  if(isClique) {
    // If it's a clique, we calc value
    int res=0;
    REP(i,n) {
      if(flag[i]) res += power[i];
    }
    return res;
  } else {
    // if it's not a clique, we set some flag to 0 and solve again
    // we already have not connected ones in i and j
    flag[i] = 0;
    int res1 = solve(flag);
    flag[i] = 1;
    flag[j] = 0;
    int res2 = solve(flag);
    return max(res1, res2);
  }
}

class MagicMolecule {
public:
int maxMagicPower(vector <int> magicPower, vector <string> magicBond) {
  power = magicPower;
  bond = magicBond;
  n=magicPower.size();

  int i;
  vector<int> flag(n);
  REP(i,n) flag[i]=1; 

  return solve(flag);
}
 |