解いた問題のソースコードと解説など。


POJ 2342 Anniversary party

問題

N人のうちから何人かパーティに招待したい。N人には上司部下の関係が存在し、これらは一つの木構造をなしている。(つまり、ある一人にたいして上司はせいぜい一人しかおらず、上司のいない人間はただ一人である)
パーティには部下とその直属の上司が同時に出席できない、という制限を設けた時、パーティの楽しさを最大化せよ。ただしパーティの楽しさは招いた人のconvivialityの和として定義される。

やりかた

木DP。
dp[idx][prevuse]:=(頂点idxを根とする部分木において、idxの親をパーティに招いたかどうかを状態として持たせた場合のconvivialityの最大値)

このように置くと、
idxの親を招いた場合にはidxを招くことはできず、
招いていない場合には、idxを招くことができるし、招かないこともできる。

convivialityがマイナスの場合はそもそも招かなくていい。
以下ソース。

int p[6001], dp[6001][2];
vector<vector<int> >g;

int dfs(int idx, bool prevuse){
  if(dp[idx][prevuse] != -1) return dp[idx][prevuse];
  
  int ret = 0;
  if(prevuse){//idxの親を招いている場合
    for(int i = 0; i < g[idx].size(); i++){
      int next = g[idx][i];
      ret += dfs(next, false);
    }
  }else{//招いていない場合
    int s1 = 0, s2 = 0;
    for(int i = 0; i < g[idx].size(); i++){
      int next = g[idx][i];
      s1 += dfs(next, false); //idxを招く
      s2 += dfs(next, true);  //idxを招かない
    }
    ret = max(s1, s2 + max(p[idx], 0));
  }
  return dp[idx][prevuse] = ret;
}


int main(int argc, char **argv){
  int N;
  scanf("%d", &N);
  g.clear();
  g.resize(N);
  for(int i = 0; i < N; i++) scanf("%d", p + i);

  int a, b;
  vector<bool> f(N, false);
  for(int i = 0; i < N - 1; i++){
    scanf("%d %d", &a, &b);
    g[b - 1].push_back(a - 1);
    f[a - 1] = true;
  }
  int s;
  for(s = 0; s < N; s++) if(!f[s]) break;//探索は根から始める
  FILL(dp, -1);

  printf("%d\n", dfs(s, false));
  scanf("%d %d", &a, &b);
  return 0;
}

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とすると答えはx(1 - \cos \frac{\theta}{2})で求められる。弧長L'はL'=x\thetaと計算でき、扇形の半径ともともとの鉄線の長さLとは2x\sin \frac{\theta}{2}=Lという関係がある。これらから\frac{\sin \frac{\theta}{2}}{\theta} = \frac{L}{2L'} = \frac{1}{2(1 + nC)}と変形する。ここからθを求めるには二分探索を使う。
θが求まればあとは代入して計算するだけ。
精度が少し厳しいのでいつもより多めにループした。
以下ソース。

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;
}
しょげないでよBaby 眠れば治る