TopCoder SRM 503

TopCoder 参加記録

Result

SystemTest Failed / Opened / Unopened
最下位

Easy ToastXToast

問題概要

トーストは種類ごとに最適な焼き時間が決まっており、それ以下だと生焼けで、
それ以上の時間を焼くと焼きすぎとなる。

生焼けのトーストの焼いた時間と、生焼けのトーストの焼いた時間が与えられるとき、
トーストは最小で何種類あるか答えよ。

解法

生焼けのトーストのうち、焼いた時間がもっとも短いものと、
焼けすぎたトーストをすべて同一の種類のトーストと考えることができる。

同様に、焼けすぎたトーストのうち焼いた時間がもっとも長いものと、
生焼けのトーストをすべて同一の種類のトーストと考えることができる。

したがって、答えは最大でも２。
更に、生焼けのトーストの最大時間が、焼きすぎのトーストの最小時間以下ならトーストは1種類で済む。


同一のトーストの対応関係が作れない場合、
すなわち、「生焼けのトーストのうち焼いた時間がもっとも短いものよりも時間が長い焼けすぎたトーストがない」、
もしくは「焼けすぎのトーストのうち焼いた時間がもっとも長いのよりも時間が短い生焼けのトーストがない」は解なしとなる。

ソースコード
class ToastXToast {
  public:
  int bake(vector <int> U, vector <int> O) {
    sort(all(U)); sort(all(O));
    if(U[0]>O[0]||U[U.size()-1]>O[O.size()-1])return -1;
    if(U[U.size()-1]<O[0])return 1;
    return 2;
  }
};

Medium KingdomXCitiesandVillages

問題概要

平面上にn個の都市とm個の村があり、それぞれの座標はcityX[i],cityY[i]と
villageX[i],villageY[j]により与えられる。
すべての村を、道路にどこかの都市に（直接または間接に）つながっているようにするのに、次の操作お繰り替えす。

  • ランダムに村を一つ選ぶ
  • 一番近い、すでにつながっている村または都市を選び、道でつなげる

このとき、すべての村をつなぐのに必要な道の長さの期待値を求めよ。

解法

村が20個程度なら典型的ビットDP.
期待値の線形性を使う。具体的にはある一つの村に注目し、
その村と、他の村との距離を近い順に並べる。
現在の村をV, 他の村を近い順にv[0],v[1],v[2],...とする。

Vv[0]の道の長さが期待値の寄与を考える。
Vv[0]が期待値に足されるのは、v[0]が先に選ばれて、Vがその後に選ばれる時である。
すなわち寄与分はd(v[0],V)/2である。

Vv[1]の道の長さの寄与分は、
v[1]が選ばれてVが選ばれて、後からv[0]が選ばれる時の分で、d(v[1],V)*/3!

Vv[2]の寄与分は
v[2]が選ばれて、Vが選ばれてv[0],v[1]が後から選ばれる時の分で、d(v[2],V)*2!/4!

……

Vが都市と接触するのは、いずれの村とも結ばれなかったときである。
以上をすべての都市についてループすればよい。

class KingdomXCitiesandVillages {
  public:
  double determineLength(vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY) {
    int nc=cityX.size(), nv=villageX.size();
    double ans=0;
    rep(i,nv){
      double near=INF, d;
      rep(j,nc)near=min(near,hypot(cityX[j]-villageX[i],cityY[j]-villageY[i]));
      vector<double> dist;
      rep(j,nv)if(i!=j){
	d=hypot(villageX[i]-villageX[j],villageY[i]-villageY[j]);
	if(d<=near)dist.pb(d);
      }
      dist.pb(near);
      sort(all(dist));

      double p=1;
      rep(j,dist.size()-1){
	ans+=dist[j]/(j+1.0)/(j+2.0);
	p-=1.0/(j+1)/(j+2);
      }
      ans+=near*p;
    }
    return ans;
  }
};