Hatena::Grouptopcoder

thorikawa@top coder

topcoder id: the_poly

2013-02-24

TopCoder - TCO13 Round1A

12:58 | はてなブックマーク - TopCoder - TCO13 Round1A - thorikawa@top coder

結果

AC/Failed System Test/Unopened 1636->1664

250を一つ撃墜できたので、なんとかレート増加。全体294位で、Round1通過できた。

250 HouseBuilding

高さを決め打ちしてBrute Forceするだけ。平均や平均±1しか見ていない人がいたので撃墜できた。

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

using namespace std;

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

class HouseBuilding {
public:
int getMinimum(vector <string> area) {
  int i,j,k;
  int n=area.size();
  int m=area[0].size();
  int res = 999999999;
  REP(k,10){
    int eff=0;
    REP(i,n) REP(j,m) {
      int c = area[i][j]-'0';
      if(c > k+1){
        eff += c-(k+1);
      } else if (c < k) {
        eff += k-c;
      }
    }
    res = min(res, eff);
  }
  return res;
}
The Frog

ジャンプ幅が最小の解は必ず、どこかの区間の右端を通るはず。(もし右端を一つも通過しないのならば、より小さい解が存在する)なので、各区間の右端をi回で到達する場合で、Brute Forceする。なお本番では、各ジャンプ幅でDまで到達できるかをチェックする際に、小数点の切り上げにceilを使っていて、ローカルでサンプルテストしている際には問題なかったのだが、サーバー上のシステムテストでは微妙な誤差があり、小数点以下が0のはずのdがd+1に切り上げられてしまうという問題があった。d-epsを切り上げていれば問題ないのだが、他にも結構な人がepsを使っておらず落ちていた模様。

っていうかサーバーとローカルで動きが違うのなんとかしたい。

#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;

const double eps = 0.0000000001;
vi l,r;
int d;
int n;

bool can (double jump) {
  int i;
  REP(i,n){
    double c1 = (double)(l[i])/jump;
    double c2 = (double)(r[i])/jump;
    double d1 = floor(c1+eps);
    double d2 = ceil(c2-eps);
    if (d2 > d1+1) {
      return false;
    }
  }
  return true;
}

class TheFrog {
public:
double getMinimum(int D, vector <int> L, vector <int> R) {
  d = D; l = L; r = R;
  n = l.size();
  double res = 9999999.0;
  
  for(int i=0; i<n; i++){
    for(double j=1; j<30030; j+=1.0){
      double jump = (double)(R[i])/j;
      if (jump < 1.0) break;
      if (can(jump)) {
        res = min(res, jump);
      }
      jump = (double)(L[i])/j;
      if (jump != 0.0) {
      //if (jump < 1.0) break;
      if (can(jump)) {
        res = min(res, jump);
      }
      }
    }
  }
  return res;
}
1000 DirectionBoard

最初に向いている方向へのコストを0、その他の方向へのコストを1として、最小費用流問題に帰着させればいいっぽい。後で解く。

2013-02-22

TopCoder - SRM Div1 Hard

16:27 | はてなブックマーク - TopCoder - SRM Div1 Hard - thorikawa@top coder

1000解いた。

1000 CandyOnDisk

2つのDiskが重なっている場合、それぞれの間を行き来可能な領域が存在する。この領域はバームクーヘンか円のIntersectionとして表現できる。全Diskを考えるとき、行き来可能な領域が重なっていれば、それらは合併することができるので、union findでつないで、(sx,sy)と(tx,ty)が行き来可能かどうかを調べることができる。

#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 parent[3000] = {-1};

int root (int i) {
  if(parent[i] == i) return i;
  else return root(parent[i]);
}
void unite (int i, int j) {
  int p1 = root(i);
  int p2 = root(j);
  if(p1==p2) return;
  else {
    parent[p2] = p1;
    return;
  }
}

inline int id(int i, int j) {
  return i*52+j;
}

class CandyOnDisk {
public:
string ableToAchieve(vector <int> rawx, vector <int> rawy, vector <int> rawr, int sx, int sy, int tx, int ty) {
  int i,j,k;

  // obvious check
  if (sx == tx && sy == ty) return "YES";
  REP(i,rawx.size()){
    double dx1 = (sx-rawx[i]);
    double dy1 = (sy-rawy[i]);
    double dx2 = (tx-rawx[i]);
    double dy2 = (ty-rawy[i]);
    double d1 = sqrt(dx1*dx1 + dy1*dy1);
    double d2 = sqrt(dx2*dx2 + dy2*dy2);
    if (d1 == d2 && d1 <= rawr[i]) {
      return "YES";
    }
  }

  // pre process
  // remove concentric circles
  vector<int> x;
  vector<int> y;
  vector<int> r;
  REP(i,rawx.size()){
    // check rawx[i] and rawy[i]
    bool exist = false;
    REP(j,x.size()){
      if (rawx[i] == x[j] && rawy[i] == y[j]) {
        r[j] = max(r[j], rawr[i]);
        exist = true;
        break;
      }
    }
    if (!exist) {
      x.push_back(rawx[i]);
      y.push_back(rawy[i]);
      r.push_back(rawr[i]);
    }
  }
  
  // initialize
  int n = x.size();
  double minr[52][52];
  double maxr[52][52];
  REP(i,n) REP(j,n) {
    minr[i][j] = 100;
    maxr[i][j] = 0;
  }
  REP(i,3000){
    parent[i] = i;
  }
  
  int sid = -1;
  int tid = -1;

  REP(i,n) {
    double sdx = sx - x[i];
    double sdy = sy - y[i];
    double tdx = tx - x[i];
    double tdy = ty - y[i];
    double sr = sqrt(sdx*sdx + sdy*sdy);
    double tr = sqrt(tdx*tdx + tdy*tdy);

    REP(j,n) {
      if (i==j) continue;
      double dx = x[i]-x[j];
      double dy = y[i]-y[j];
      double d = sqrt(dx*dx + dy*dy);
      if (r[i] >= d+r[j]) {
        // r[i] covers r[j]
        minr[i][j] = max(0.0, d-r[j]);
        maxr[i][j] = d+r[j];
      } else if (r[j] >= d+r[i]) {
        // r[j] covers r[i]
        minr[i][j] = 0.0;
        maxr[i][j] = r[i];
      } else if (d <= r[i]+r[j]) {
        // intersect
        minr[i][j] = max(0.0, d-r[j]);
        maxr[i][j] = r[i];
      }
      
      if (sr <= maxr[i][j] && sr >= minr[i][j]) {
        sid = id(i,j);
      }
      if (tr <= maxr[i][j] && tr >= minr[i][j]) {
        tid = id(i,j);
      }
    }
  }
  
  // union find
  REP(i,n) {
    REP(j,i) {
      if (maxr[i][j] >= minr[i][j]) {
        unite(id(i,j), id(j,i));
      }
    }
  }
  REP(i,n) {
    REP(j,n) {
      if (i==j) continue;
      REP(k,n) {
        // compare (i,k) and (j,k) 
        if (i==k || j==k) continue;
        if (maxr[k][i] < minr[k][i]) {
          continue;
        }
        if (maxr[k][j] < minr[k][j]) {
          continue;
        }
        if (!(maxr[k][i] < minr[k][j] || maxr[k][j] < minr[k][i])) {
          // intersect
          unite(id(k,i), id(k,j));
        }
      }
    }
  }
  if (sid == -1 || tid == -1) {
    return "NO";
  }
  if (root(sid) == root(tid)) {
    return "YES";
  }
  
  return "NO";
}


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);
}

2013-02-19

TopCoder - SRM567 Div1

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

250 TheSquareRootDilemma

一見して簡単そうだが、計算量減らすのが思ったより難しかった。式を展開すると、ijが平方数になる1<=i<=N,1<=j<=Mのペア数を計算すればよい。総当りは計算量O(N*M)で間に合わないが、ペアのうち片方をiで固定して考えると、i*a=平方数となる最小のaを求めてやれば、あとは、a*平方数がペアのもう片方になり、これは計算量O(N*log(M))で求められる。

#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 long long ll;

class TheSquareRootDilemma {
public:
int countPairs(int n, int m) {
  int res=0;
  for(ll i=1; i<=n; i++){
    ll tmp = i;
    ll smallest = 1;
    for(ll j=2; j*j<=i; j++){
      int e = 0;
      while((tmp > 1) && (tmp%j==0)){
        e++;
        tmp /= j;
      }
      if(e%2) smallest *= j;
    }
    smallest *= tmp;
    for(ll j=1; j*j*smallest<=m; j++){
      res++;
    }
  }
  return res;
}

2013-02-18

TopCoder - TCO 2012 Round 3A

| 14:54 | はてなブックマーク -  TopCoder - TCO 2012 Round 3A - thorikawa@top coder

グラフ強化月間と題して自習。TCO 2012 Round3Aは250,600ともにグラフ問題。

250 ChromaticNumber

各頂点から出ていくエッジが最低でもN-3あることから、逆にエッジがない部分をエッジとしてグラフを反転してやる(つまりエッジが無い=色が異なる)。この反転グラフを連結成分分解すると、各連結成分間にはエッジが存在しないので、同じ色は使われず、各連結成分ごとに必要な色数を求めて足せば、求める答えとなる。

各連結成分は、各頂点から出て行くエッジ数が高々2であることから、分岐のない一本道のグラフとなり、頂点数が3でcyclicの場合に1色、それ以外は2頂点ごとに色を変えていくことになるので、頂点数nに対しn/2+n%2色が必要となる。

ソース

https://gist.github.com/thorikawa/4975164

600 FoxAndCake

あとでやる。