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として、最小費用流問題に帰着させればいいっぽい。後で解く。