POJ 2536 Gopher II

問題

n匹のネズミの位置と、m匹のネズミ穴の位置が与えられる。タカがネズミを狙っており、s秒たった時点で穴に隠れていないネズミは捕食される。すべてのネズミは速度vで動くことができ、一つの穴には一匹のネズミだけが隠れることができる。捕食されるネズミの数を最小化せよ。

やりかた

各ネズミと各ネズミ穴の間でs秒以内に到達できるペアに辺を張って、二部グラフを作って二部マッチングすると逃げ切れるネズミの数を最大化できる。

以下ソース。

double gx[100], gy[100], hx[100], hy[100];
vector<vector<int> > G; //bidirection

bool augment(int u, 
	     vector<int> &match, vector<bool> &vis){
  vis[u] = true;
  for(int i = 0; i < G[u].size(); i++){
    int v = G[u][i], w = match[v];
    if(w == -1 || (!vis[w] && augment(w, match, vis))){
      match[u] = v, match[v] = u;
      return true;
    }
  }
  return false;
}

int bipartite_matching(){
  int V = G.size(), ret = 0;
  vector<int> match(V, -1);
  for(int i = 0; i < V; i++){
    if(match[i] != -1) continue;
    vector<bool> vis(V, false);
    if(augment(i, match, vis)) ret++;
  }
  return ret;
}

int main(int argc, char **argv){
  int n, m, s, v;
  while(cin >> n >> m >> s >> v){
    for(int i = 0; i < n; i++) cin >> gx[i] >> gy[i];
    for(int i = 0; i < m; i++) cin >> hx[i] >> hy[i];

    G.clear();
    G.resize(n + m);
    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
	double d = sqrt(pow(gx[i] - hx[j], 2.0) + pow(gy[i] - hy[j], 2.0));
	if(d / v < s){
	  G[i].push_back(n + j);
	  G[n + j].push_back(i);
	}
      }
    }
    cout << n - bipartite_matching() << endl;
  }
  return 0;
}

POJ 1975 Median Weight Bead

問題

1からNの数字が書かれたビーズがある。2つビーズについての重さの関係の情報がM個ある。N個のビーズのうち重さが中央値になりえないものの個数を求めよ。

やりかた

一種のトポロジカルソート。自分より重いビーズに辺を張って、重さの関係をグラフに置き換える。自分から到達可能な点が(N+1)/2以上あればメディアンたりえないし、自分に到達可能な点が(N+1)/2以上あっても同様。到達可能性を調べるのはワーシャルフロイドでやった。グラフは木構造でない場合ももちろんあるのでDFSではそこ注意。

以下ソース。

bool d[100][100];

int main(int argc, char **argv){
  int T;
  cin >> T;
  while(T--){
    int N, M, s, t;
    cin >> N >> M;
    memset(d, false, sizeof(d));
    for(int i = 0; i < N; i++) d[i][i] = true;
    for(int i = 0; i < M; i++){
      cin >> s >> t; s--, t--;
      d[t][s] = true;
    }
    for(int k = 0; k < N; k++)
      for(int i = 0; i < N; i++)
	for(int j = 0; j < N; j++)
	  d[i][j] |= (d[i][k] && d[k][j]);

    int ans = 0;
    for(int i = 0; i < N; i++){
      int cnt1 = 0, cnt2 = 0;
      for(int j = 0; j < N; j++){
	cnt1 += d[i][j];
	cnt2 += d[j][i];
      }
      ans += (cnt1 > (N + 1) / 2);
      ans += (cnt2 > (N + 1) / 2);
    }
    cout << ans << endl;
  }
}

POJ 2513 Colored Sticks

問題

両端にそれぞれ色が塗られている棒が複数与えられ、色が同じ棒の端同士を連結して一本の棒にすることができる。与えられた棒をすべて連結することはできるか答えよ。

やりかた

やっていることはしりとりと同じ。各色をグラフ上の頂点とみなし、棒を辺を考えれば、問題はすべての辺を一回ずつ通ることができるかという問いになる。これは準オイラーグラフ以上になっているかどうか判定すればいい。よって各頂点の次数のうち奇数になる頂点が2以下になるかどうか調べればいい。
なお、そのまえにグラフが連結であること調べておく必要がある。色はハッシュにしてintで管理する。

以下ソース。

vector<int> g[300000];
int enc[300000];
bool vis[300000];
int V;

int base = 1007;
int mod = 273113;

//文字列をハッシュに変換
int ro_hash(char *s){
  int L = strlen(s);
  int hash = 0;
  for(int i = 0; i < L; i++) hash = (hash + s[i]) * base % mod;
  if(enc[hash] != -1) return enc[hash];
  return enc[hash] = V++;
}

//連結性の判定
void rec(int idx, int prev){
  vis[idx] = true;
  for(int i = 0; i < g[idx].size(); i++)
    if(g[idx][i] != prev && !vis[g[idx][i]])
      rec(g[idx][i], idx);
  return;
}

int main(){
  char s[15], t[15];
  V = 0;
  memset(enc, -1, sizeof(enc));
  memset(vis, false, sizeof(vis));
  while(~scanf("%s %s", s, t)){
    int fr = ro_hash(s);
    int to = ro_hash(t);
    g[fr].push_back(to);
    g[to].push_back(fr);
  }
  
  rec(0, -1);
  if(count(vis, vis + V, false) != 0){
    printf("Impossible\n");
    return 0;
  }

  int odd = 0;
  for(int i = 0; i < V; i++) //次数が奇数である頂点数を数える
    odd += (g[i].size() % 2);
  printf("%s\n", odd <= 2 ? "Possible" : "Impossible");
}

POJ 2472 106 miles to Chicago

問題

無向グラフの情報が与えられる。始点から終点まで辺のコストをかけ合わせたものがパスのコストになる。コストを最大化せよ。

やりかた

辺のコストにlogをかければコストの積を和に変換できる。あとはただの最小経路問題。

以下ソース。

//ダイクストラのコードは略
int main(int argc, char **argv){
  int V, E;
  while(scanf("%d", &V), V){
    scanf("%d", &E);
    g.clear();
    g.resize(V);
    for(int i = 0; i < E; i++){
      int a, b, c;
      scanf("%d %d %d", &a, &b, &c);
      add_edge(a - 1, b - 1, -log(c / 100.0));
    }
    double d = -dijkstra(g, 0, V - 1);
    printf("%.6f percent\n", 100 * exp(d));
  }
}

POJ 1855 Mint

問題

数種類の長さの棒がある。各種類とも棒は無尽蔵にあるとして良い。棒をつなぎ合わせて4本足の机を作る。各足は同じ種類の木を使い、4本の足の長さが揃うように作る時、決められた高さ以下で作れる最高の高さと、決められた高さ以上で作れる最小の高さを求めよ。

やりかた

ある4種類を選んだ時、その4種類の長さの公倍数のうち、決められた高さ以下で最高になるものと、高さ以上で最低になるものを計算する。すべての4種類のパターンについてこの計算を行い、最高値と最小値を求める。
長さの種類数がが50以下なので4重ループで通る。

以下ソース。

inline ll gcd(ll a, ll b){ return b == 0 ? a : gcd(b, a % b); }
inline ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }

int e[51];

int main(int argc, char **argv){
  int N, M;
  while(cin >> N >> M, N + M){
    for(int i = 0; i < N; i++) cin >> e[i];
    sort(e, e + N);
    int v[4];
    while(M--){
      ll T; cin >> T;
      ll miv = 0, mav = LLINF;
      for(int a = 0; a < N; a++){
	for(int b = a + 1; b < N; b++){
	  for(int c = b + 1; c < N; c++){
	    for(int d = c + 1; d < N; d++){
	      v[0] = e[a], v[1] = e[b], v[2] = e[c], v[3] = e[d];
	      ll g = v[0];
	      for(int j = 0; j < 4; j++)
		g = lcm(g, v[j]);
	      
	      miv = max(miv, T / g * g);
	      mav = min(mav, (T + g - 1) / g * g);
	    }
	  }
	}
      }
      cout << miv << " " << mav << endl;
    }      
  }
  return 0;
}

POJ 1905 Expanding Rods

問題

長さLの鉄線をn度で熱すると長さがL*(1+n*C)に変化する。Cは膨張係数である。この鉄線を向かい合わせの壁に取り付けて熱すると膨張して弧を描くようにしなる。熱したときの鉄線の中心部の縦方向への変位を求めよ。

やりかた

弧になったときの弧長をL'、中心角をθとし、半径をxとすると答えはで求められる。弧長L'はと計算でき、扇形の半径ともともとの鉄線の長さLとはという関係がある。これらからと変形する。ここからθを求めるには二分探索を使う。
θが求まればあとは代入して計算するだけ。
精度が少し厳しいのでいつもより多めにループした。
以下ソース。

int main(int argc, char **argv){
  double l, n, c;
  while(cin >> l >> n >> c){
    if(l < 0 && n < 0 && c < 0) break;
    
    double ub = acos(( double)-1), lb = 0;
    for(int i = 0; i < 10000; i++){
      double mid = (ub + lb) * 0.5;
      double x = sin(0.5 * mid) / mid;
      double y = 0.5 / (1.0 + n * c);
      if(x > y) lb = mid;
      else ub = mid;
    }
    cout.precision(3);
    cout.setf(ios::fixed);
    cout << ((1.0 - cos(0.5 * ub)) * l * (1.0 + n * c) / ub) << endl;
  }
  return 0;
}

POJ 1505 Copying Books

問題

要素数mの数列をk個の連続する数列に分割する。分割したそれぞれの数列の要素の和を計算し、そのうち最大となる値を最小化するように数列を分割したい。この条件をみたすように数列を分割して出力せよ。ただし複数の分割方法がある場合には、分割したはじめの数列の和のほうからなるべく小さくなるようにという方針で分割せよ。

やりかた

分割した数列中の和の最大値をXとすると、Xを大きくすると分割数kは小さくなる。なので二分探索で最適な和は計算することができる。
ただしこの問題は頭の方から小さく分割しろという条件が面倒。これには、数列を後ろの方から条件を満たしつつ、貪欲に大きく分割した後、余った分割数分、今度は数列の頭の方から細かく分割していくことで実現できる。

例えば2ケース目の
5 4
100 100 100 100 100
という入力では最小の最大和は200と求まるので、後ろのからひとまず
100 / 100 100 / 100 100
と分割する。分割数が1つ余っているので、今度は頭の方から分割できるところを見つけ次第余った数だけ分割すると答えになる。
100 / 100 / 100 / 100 100

以下ソース。

int m, k;
vector<ll> page;

int C(ll v){
  ll sum = 0;
  int cnt = 0;
  for(int i = m - 1; i >= 0; i--){
    if(v < page[i]) return INF;
    if(sum + page[i] <= v){
      sum += page[i];
    }else{
      cnt++;
      sum = page[i];
    }
  }
  return cnt;
}

int main(int argc, char **argv){
  int n;
  cin >> n;
  while(n--){
    cin >> m >> k;
    page.resize(m);

    ll ub = 0LL, lb = 0LL, div;
    for(int i = 0; i < m; i++){ 
      cin >> page[i];
      ub += page[i];
    }
    
    while(lb < ub){
      ll mid = (ub + lb) / 2;
      div = C(mid);
      if(div + 1 <= k) ub = mid;
      else lb = mid + 1;
    }
    reverse(ALL(page));
    ll sum = 0, rem = k - C(ub) - 1;
    vector<int> a;
    //cout << ub << " " << C(ub) << endl;
    for(int i = 0; i < page.size(); i++){
      if(sum + page[i] > ub){
	sum = 0;
	a.push_back(-1);
      }
      sum += page[i];
      a.push_back(page[i]);
    }
    reverse(ALL(a));
    vector<int> b;
    for(int i = 0; i < a.size(); i++){
      b.push_back(a[i]);
      if(i < a.size() - 1){
	if(rem && (a[i] != -1 && a[i + 1] != -1)){
	  rem--;
	  b.push_back(-1);
	}
      }
    }
    for(int i = 0; i < b.size(); i++)
      if(b[i] == -1) cout << "/ ";
      else cout << b[i] << " ";
    cout << endl;
  }
  return 0;
}