読者です 読者をやめる 読者になる 読者になる

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


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

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

POJ 1985 Cow Marathon

問題

無向木の情報が与えられる。同じ辺を2度辿らないように頂点間を移動する時、もっとも距離の遠い2点間の距離を求めよ。

やりかた

無向木の直径を求める問題に他ならない。直径の求め方は、てきとうな頂点から深さ優先探索を始めて最遠の頂点uを求める。つづいてその最遠の頂点uから始めて、最遠の頂点vを求める。するとu-vの頂点間が最遠の距離になっている。

以下ソース。

struct edge{
  int to, cost;
};

vector<edge> g[40001];
int dist[40001];

void dfs(int cur, int prev, int cost){
  dist[cur] = cost;
  for(int i = 0; i < g[cur].size(); i++)
    if(g[cur][i].to != prev) 
      dfs(g[cur][i].to, cur, cost + g[cur][i].cost);
}

int main(int argc, char **argv){
  int V, E;
  scanf("%d %d", &V, &E);

  for(int i = 0; i < E; i++){
    int s, t, c; char dir;
    scanf("%d %d %d %c", &s, &t, &c, &dir);
    g[s - 1].push_back((edge){t - 1, c});
    g[t - 1].push_back((edge){s - 1, c});
  }

  fill(dist, dist + V, 0);
  dfs(0, -1, 0);;

  int u = max_element(dist, dist + V) - dist;
  fill(dist, dist + V, 0);
  dfs(u, -1, 0);
  printf("%d\n", *max_element(dist, dist + V));
  return 0;
}

POJ 3510 A Tale from the Dark Side of the Moon

問題

文字列が一行ずつ与えられる。一行ごとに以下の処理を行って出力せよ。

  • アルファベット小文字とスペース以外は削除
  • "dd"という文字列があったら"p"に変換("ddd"という入力はないものとする)
  • "ei"という文字列があったら"ie"に変換(ただし直前の文字が'c'であれば変換しない)
  • "pink"という文字列があったら"floyd"に変換
  • "EOF"という文字列があったらそこで処理を中断して終了
やりかた

ただやるだけではあるけど、それぞれの処理を初期の文字列に対して並行して行う必要がある。文字列を逐次的に処理すると変換後の文字列を再度変換してしまうので注意。例えば"ddink"は"pink"に変換されるが、逐次的に変換してしまうと"ddink" -> "pink" -> "floyd" になってしまう。"eiieii"なども注意。"iieiieは間違いで"正しくは"ieiiei"になる。
あとEOFは文字列の途中で出てくることがあり、その場合はそこまでを変換して出力する。

以下ソース。

void strReplace(string &str, const string &from, const string &to){
  string::size_type pos = 0;
  while((pos = str.find(from, pos)) != string::npos){
    str.replace(pos, from.length(), to);
    pos += to.length();
  }
}

int main(int argc, char **argv){
  string s;
  while(getline(cin, s)){
    int idx = s.find("EOF");
    bool final = false;
    if(idx != string::npos){
      s = s.substr(0, idx);
      final = true;
    }

    strReplace(s, "dd", "dddpddd");
    strReplace(s, "pink", "floyd");
    strReplace(s, "dddpddd", "p");

    for(int i = 1; i < s.size(); i++){
      if(s[i - 1] == 'e' && s[i] == 'i'){
	if(i == 1 || (2 <= i && s[i - 2] != 'c')){
	  s[i - 1] = 'i', s[i] = 'e'; i++;
	}
      }
    }

    for(unsigned char c = 0; c < 0xff; c++){
      if(('a' <= c && c <= 'z') || c == ' ') continue;
      string d; d += c;
      strReplace(s, d, "");
    }
    cout << s << endl;
    if(final) break;
  }
  return 0;
}

今見ると変数名にfinalとかつけてしまった。もしPOJがc++11だったらCompile Errorになってた。

POJ 1129 Channel Allocation

問題

頂点と辺の情報が与えられる。最小で何色で頂点を塗ることができるか答えよ。

やりかた

四色定理から必ず4以下になる。
色を数値で管理して、深さ優先探索でグラフを探索する。探索中に次に訪れる点に隣接している点の色で使っていない色のうち、最も値の小さい色を次に訪れる点の色にすればいい。すべての点で探索が終わったら使った色の数を数える。

以下ソース。

int color[30];
bool adj[30][30];
int n;

int ret(int idx){
  bool used[4] = {false};
  for(int i = 0; i < n; i++)
    if(adj[idx][i] && color[i] != -1)
      used[color[i]] = true;
  for(int i = 0; i < 4; i++)
    if(!used[i]) return i;
}
void dfs(int i){
  for(int j = 0; j < n; j++){
    if(!adj[i][j] || color[j] != -1) continue;
    color[j] = ret(j);
    dfs(j);
  }
  return;
}

int main(int argc, char **argv){
  while(scanf("%d", &n), n){
    FILL(color, -1);
    FILL(adj, false);
    for(int k = 0; k <n; k++){
      char s[30]; scanf("%s", s);    
      for(int i = 2; i < strlen(s); i++)
	adj[s[0] - 'A'][s[i] - 'A'] = true;
    }

    for(int i = 0; i < n; i++){
      if(color[i] != -1) continue;
      color[i] = 0;
      dfs(i);
    }

    set<int> r(color, color + n);
    if(r.size() == 1)
      printf("%d channel needed.\n", r.size());
    else
      printf("%d channels needed.\n", r.size());
  }
  return 0;
}
しょげないでよBaby 眠れば治る