POJ 2782 Bin Packing

問題

アイテムがN個あり、それぞれの重さが与えられる。これらのアイテムをビンに詰めたいとする。一つのビンにたいして最大で2個までのアイテムを詰められる。このとき必要な最小のビンの数を求めよ。ただし一つのビンに詰めるアイテムの重さの和がLより大きくなってはいけない。

やりかた

ビンパッキング問題なので普通なら効率的にはできないが、ビンに入れられるアイテム数がせいぜい2なので貪欲で解ける。最小の重みのアイテムと、合わせてビンに詰めることができる最大の重みを持つアイテムを見つけてこれら2つを消去し、ビン1つにカウントする。合わせて詰められるアイテムが見つからない場合は単独で消去し、ビン1つにカウントする。これをアイテムがなくなるまで繰り返せばいい。アイテムはmultisetで管理し、条件に合う最大重みのアイテムを見つける処理はlower_boundで二分探索する。

以下ソース。

#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#define ALL(c) (c).begin(), (c).end()

using namespace std;

int main(){
  int N, L;
  scanf("%d %d", &N, &L);

  multiset<int> x;
  for(int i = 0; i < N; i++){
    int a;
    scanf("%d", &a);
    x.insert(a);
  }

  int ans = 0;
  while(!x.empty()){
    int b = L - *x.begin();//計算上詰められる最大重み
    multiset<int>::iterator it = x.begin();
    it =  x.upper_bound(b);
    if(it != x.begin()) it--;
    
    if(it != x.begin()) x.erase(it); //抱き合わせできるものが見つかった場合は消す
    x.erase(x.begin());//今見ているアイテムを消す
    ans++;
  }

  printf("%d\n", ans);
  return 0;
}

POJ 3862 Business Center

問題

エレベータがm台あり、各エレベータには昇降用のボタンが2つだけついている。エレベータiの上昇ボタンを押すとu[i]階上がり、下降ボタンを押すとd[i]階下がる。階数は無限にあるが、0階より下の階はない。m台のエレベータのうちのいずれか一台のエレベータを選んで、n回昇降ボタンを押した上で到達することができるもっとも低層の階（ただし1階以上）を求めよ。

やりかた

上昇ボタンをx回、下降ボタンをn-x回押してp階にたどり着けるとするととなる。xについて解くと xは整数であるから分子は分母で割り切れる必要があり、これを満たすようなpは になる。すべてのエレベータでpを計算して最小値を求めればいい。

以下ソース。

int main(){
  int n, m, u, d;
  scanf("%d %d", &n, &m);

  int ans = INF;
  for(int i = 0; i < m; i++){
    scanf("%d %d", &u, &d);
    ans = min(ans, u + d - (d * n) % (u + d));
  }
  printf("%d\n", ans);
  return 0;
}

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));
  }
}