Hatena::Grouptopcoder

blu_rayの日記

2011-11-13

Codeforces Beta Round #93 Div2

| 00:46

ooox-

A. Wasted Time / Accpeted(00:12) / 476

1問目にして問題文が長い…。

心が折れそうになるけど、ただ距離を足してくだけ。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int n, k, x[102], y[102];

double dist(int _ax, int _ay, int _bx, int _by) {
  double ax = _ax, ay = _ay, bx = _bx, by = _by;
  return sqrt( (ax - bx) * (ax - bx) + (ay - by) * (ay - by) );
}

int main() {
  cin >> n >> k;
  rep (i,n) {
    cin >> x[i] >> y[i];
  }
  int _x = x[0], _y = y[0];
  double times = 0;
  for (int i = 1; i < n; ++i) {
    times += dist(_x, _y, x[i], y[i]) / 50.0;
    _x = x[i], _y = y[i];
  }
  times *= k;
  printf("%.8lf\n", times);
  return 0;
}

B. Canvas Frames / Accepted(00:18) / 878

n個の数列が与えられて、ペアの数 / 2を答える問題。

nが最大100なので、下の愚直なコードでも十分通る。こっちがAじゃないか。

int main() {
  cin >> n;
  rep (i,n) cin >> a[i];

  int ans = 0;  
  for (int i = 0; i < n-1; ++i) {
    if (a[i] == -1) continue;
    for (int j = i+1; j < n; ++j) {
      if (a[i] == a[j]) {
        ans++;
        a[i] = a[j] = -1;
        break;
      }
    }
  }
  cout << ans / 2 << endl;  
  return 0;
}

C. Hot Bath / Accepted(01:50) / 690

適当に、t0に近づくようにお湯の量と水の量をちょっとずつ出してくようにして解を求めるようにしたら通った。

(t1 * y1 + t2 * y2) / (y1 + y2) = t0となる、y1, y2を求められればそこで探索を打ちきっていいんだけどめんどかったので省略。

多分、whileループが最大2*10^6くらいのはずなので、計算量的には大丈夫だと思った。

あとはコーナーケースに気をつける。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

const double eps = 1e-8;
int t1, t2, x1, x2, t0;

double derive(int _y1, int _y2) {
  double _t1 = t1, _t2 = t2, y1 = _y1, y2 = _y2;
  double ret = (t1 * y1 + t2 * y2) / (y1 + y2);
  return ret;
}

int main() {
  while (cin >> t1 >> t2 >> x1 >> x2 >> t0) {

    
    if (t1 == t2 && t1 == t0) {
      cout << x1 << " " << x2 << endl; continue;
    }

    if (t1 >= t0) {
      cout << x1 << " " << 0 << endl; continue;
    }
    
    if (t2 == t0) {
      cout << 0 << " " << x2 << endl; continue;
    }
    
    double min_dist = double(1 << 30);

    int y1 = 0, y2 = 1;
    int ny1 = -1, ny2 = -1;

    while (true) {
      double t = derive(y1, y2);
      double dist = t - t0;
      //printf("%d, %d : %lf\n", y1, y2, t);
      if (dist >= 0 && dist < min_dist) {
        ny1 = y1, ny2 = y2;
        min_dist = dist;
      }
      if (t > t0) {
        y1++;
      } else {
        y2++;
      }
      if (y1 > x1 || y2 > x2) {
        y1 = ny1, y2 = ny2;
        break;
      }
    }
    
    int t = 1;
    for (; t * y1 <= x1 && t * y2 <= x2; ++t);
    if (t > 1) t--;
    y1 *= t;
    y2 *= t;
    
    cout << y1 << " " << y2 << endl;
  }  
  return 0;
}

D. Password / WA(TLE)

Cを解いている人の数がなかなか伸びない中、Dを解いている人の数が増えてったので出したら通ってしまったのだけど、TLE解で10^12だった。。Cが解けずにてんぱっていて見積もってなかった。

二分探索か、場所を覚えておけばいいっぽい。

rate := 1658(+73)

これってDiv1なのか...な。

rateごとのクラス名が軍人の階級的なものから変更されたけど、Expertは自分にとっちゃ畏れ多い