EAGLE 雑記 このページをアンテナに追加 RSSフィード

Sat January 29, 2011

[] 3345 -- Bribing FIPA

http://poj.org/problem?id=3345

いくつかの木が与えられ,その各ノードにコストが割り振られている.

全部で N 個のノードの中から M 個以上の頂点を選んだときの,コストの和の最小値を求めたい.

ただしあるノードを選んだとき,そのノードのコストで,そのノードを根とする部分木の全ノードを取れるとする.

サンプルだと,Boland を取ることにするとコスト20で Boland と Aland の2つを取れることになる.

1 <= N <= 200, 0 <= M <= N


先日の練習会で聞いた解説の方針で解いた.ただし微妙に DP 表のとり方を変えた.

ノードの数を価値として単純にナップザック問題として解こうとすると,子ノードを二重に取ってしまってアウト.

とりあえず無限大のコストを持つダミーノードを導入して,これを根とする1つの木にまとめた状態で考える.

ノード

dp[i] = このノードを根とする部分木の中から i 個以上取ったときの最小コスト

というような DP 表を持たせ,下のほうから再帰的に埋めていく.

dp[i] の初期値は,部分木のノードの数を m,ノードのコストを c とすると

  • dp[i] = 0 if i == 0
  • dp[i] = c if 1 <= i <= m
  • dp[i] = ∞ otherwise

となる.

あとはナップザック的に各子ノードの DP 表 dp_child について

dp[i] = min{ dp[i-j] + dp_child[j] } (1 <= j <= N)

と更新していけば,ダミーノードの DP 表の M 番目の値が答えとなる.


以下ソース.tree[0] がダミーノード.solve はノード n を根とする部分木のノード数を返している.

#include <iostream>
#include <sstream>
#include <vector>
#include <map>
using namespace std;
static const int INF = 100000000;

struct node
{
  int cost;
  vector<int> children;
  vector<int> dp;
};

int solve(vector<node>& tree, int M, int n = 0)
{
  int value = 1;
  for (vector<int>::const_iterator it(tree[n].children.begin()); it != tree[n].children.end(); ++it) {
    value += solve(tree, M, *it);
  }

  const int N = tree.size();
  vector<int>& dp = tree[n].dp;
  dp.resize(N+1, INF);
  dp[0] = 0;
  for (int i = 1; i <= value; i++) {
    dp[i] = tree[n].cost;
  }
  for (vector<int>::const_iterator it(tree[n].children.begin()); it != tree[n].children.end(); ++it) {
    const vector<int>& dp_child = tree[*it].dp;
    for (int i = value; i >= 0; i--) {
      for (int j = 1; j <= N; j++) {
        if (i-j >= 0) {
          dp[i] = min(dp[i], dp[i-j] + dp_child[j]);
        }
      }
    }
  }
  return value;
}

int main()
{
  string s;
  while (getline(cin, s) && s != "#") {
    int N, M;
    {
      istringstream iss(s);
      iss >> N >> M;
    }
    map<string,int> m;
    vector<node> tree(N+1);
    tree[0].cost = INF;
    vector<bool> owned(N+1, false);
    for (int i = 0; i < N; i++) {
      getline(cin, s);
      istringstream iss(s);
      string t;
      int c;
      iss >> t >> c;
      int id;
      map<string,int>::const_iterator it = m.find(t);
      if (it == m.end()) {
        id = m.size()+1;
        m.insert(make_pair(t, id));
      } else {
        id = it->second;
      }
      tree[id].cost = c;

      while (iss >> t) {
        it = m.find(t);
        int j;
        if (it == m.end()) {
          j = m.size()+1;
          m.insert(make_pair(t, j));
        } else {
          j = it->second;
        }
        tree[id].children.push_back(j);
        owned[j] = true;
      }
    }
    for (int i = 1; i <= N; i++) {
      if (!owned[i]) {
        tree[0].children.push_back(i);
      }
    }
    solve(tree, M);
    cout << tree[0].dp[M] << endl;
  }
  return 0;
}

Wed March 10, 2010

[] 3255 -- Roadblocks

http://acm.pku.edu.cn/JudgeOnline/problem?id=3255

重み付きグラフが与えられて,2番目にコストが小さい経路のコストを出力する問題.


1番コストが小さいものなら普通のダイクストラ法でいいのだが,今回は2番目なので各頂点に対して2番目までのコストを覚えておいて更新するようにして解いた.

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

template <typename T>
T dijkstra(const vector<vector<pair<int,T> > >& g, int start, int goal)
{
  const int N = g.size();
  vector<T> costs1(N, numeric_limits<T>::max()), costs2(N, numeric_limits<T>::max());
  priority_queue<pair<T,int> > q;
  q.push(make_pair(0, start));
  while (!q.empty()) {
    const T cost = -q.top().first;
    const int node = q.top().second;
    q.pop();
    if (costs2[node] <= cost) {
      continue;
    }
    if (costs1[node] > cost) {
      costs1[node] = cost;
    } else {
      costs2[node] = cost;
    }

    for (typename vector<pair<int,T> >::const_iterator it(g[node].begin()); it != g[node].end(); ++it) {
      q.push(make_pair(-(cost + it->second), it->first));
    }
  }
  return costs2[goal];
}

int main()
{
  int N, R;
  cin >> N >> R;
  vector<vector<pair<int,int> > > g(N);
  for (int i = 0; i < R; i++) {
    int a, b, d;
    cin >> a >> b >> d;
    g[a-1].push_back(make_pair(b-1, d));
    g[b-1].push_back(make_pair(a-1, d));
  }
  cout << dijkstra(g, 0, N-1) << endl;
  return 0;
}

Thu March 04, 2010

[] 3615 -- Cow Hurdles

http://acm.pku.edu.cn/JudgeOnline/problem?id=3615

N 個の駅があり,M 本の一方通行の道が繋いでいて,それぞれの道には高さ H_i のハードルがあるとする.

駅 A_i から駅 B_i まで行くとき,途中で越えなければならないハードルの最大の高さの最小値を出力せよという問題.

もし A_i から B_i までの経路が存在しない場合は -1 を出力する.


いわゆる最短経路問題のひとつ.

複数の駅のペア間の最小値を問われるので,任意の2ノード間の最短経路を求めることができる Warshall-Floyd 法というアルゴリズムで解いた.

http://ja.wikipedia.org/wiki/%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB-%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95

Wikipedia を見ながら実装.アイデアはシンプルでわかりやすいと思う.

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

vector<vector<int> > floyd(const vector<vector<int> >& g, const vector<vector<int> >& w)
{
  const int N = g.size();
  vector<vector<int> > dist(N+1, vector<int>(N+1, numeric_limits<int>::max()));
  for (int i = 1; i <= N; i++) {
    for (int j = 0; j < g[i].size(); j++) {
      const int to = g[i][j];
      dist[i][to] = w[i][j];
    }
  }

  for (int k = 1; k <= N; k++) {
    for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= N; j++) {
        dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));
      }
    }
  }
  return dist;
}

int main()
{
  int N, M, T;
  cin >> N >> M >> T;
  vector<vector<int> > g(N+1);
  vector<vector<int> > w(N+1);
  for (int i = 0; i < M; i++) {
    int s, e, h;
    cin >> s >> e >> h;
    g[s].push_back(e);
    w[s].push_back(h);
  }

  const vector<vector<int> > dist = floyd(g, w);
  for (int i = 0; i < T; i++) {
    int a, b;
    cin >> a >> b;
    int c = dist[a][b];
    if (c == numeric_limits<int>::max()) {
      cout << -1 << endl;
    } else {
      cout << c << endl;
    }
  }
  return 0;
}

Sun February 28, 2010

[] 2591 -- Set Definition

http://acm.pku.edu.cn/JudgeOnline/problem?id=2591

次のように定められた集合 S の N 番目(昇順)の要素を出力する問題.

  • 1 は S の要素である
  • x が S の要素ならば,2x + 1 と 3x + 1 も S の要素である
  • その他は S の要素でない

N の上限が 10000000 なので,最初に 10000000 番目まで S の要素を作っておいて答えた.

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
  static const int N = 10000000;
  vector<int> v(N);
  int a = 0, b = 0;
  v[0] = 1;
  for (int i = 1; i < N; i++) {
    int x = min(2*v[a]+1, 3*v[b]+1);
    if (x == 2*v[a]+1) {
      a++;
    }
    if (x == 3*v[b]+1) {
      b++;
    }
    v[i] = x;
  }

  int n;
  while (cin >> n) {
    cout << v[n-1] << endl;
  }
  return 0;
}

ちなみに Haskell なら以下のようにもっとシンプルに定義通りに書ける (これを言いたかっただけ).

s = 1 : merge (map (\x -> 2*x+1) s) (map (\x -> 3*x+1) s)
  where
    merge a@(x:xs) b@(y:ys) =
      case compare x y of
        LT -> x : merge xs b
        EQ -> x : merge xs ys
        GT -> y : merge a ys

main = interact (unlines . map (show . (s !!) . subtract 1 . read) . lines)

Wed February 24, 2010

[] 3014 -- Cake Pieces and Plates

http://acm.pku.edu.cn/JudgeOnline/problem?id=3014


整数 n, m (1 ≦ n, m ≦ 4500) が与えられて,m を n 個の整数の和に何通りに分割できるか答える問題.

ただし答えは非常に大きくなりうるので,答えを 1000000007 で割った余りを出力する.


DP で解いた.

j を i 個の整数の和に分割する方法が dp[i][j] 通りだとすると,

i == 1 のとき

j を 1 個に分割するのは (j) だけなので,dp[1][j] = 1

j == 1 のとき

1 を i 個に分割するのは (0,..,0,1) だけなので dp[i][1] = 1

i < j のとき
  • j を i-1 個に分割し,それに 0 を加えることで j を i 個に分割できるので dp[i-1][j] 通り.
  • i-j を j 個に分割し,それぞれの要素に 1 を加えることで dp[i-1][j-i] 通り.

よって dp[i-1][j] + dp[i][j-i] 通りになる.

例えば i = 2, j = 4 のとき,

  • 4 を 1 個に分割して (4).これに 0 を加えて (0,4) の 1 通り
  • 2 を 2 個に分割して (0,2), (1,1).それぞれの要素に 1 を加えて (1,3), (2,2) の 2通り

となる.

i > j のとき

j-i が整数でなくなるので,i < j の1つ目の場合だけ考えればいいので dp[i-1][j] 通り

i == j のとき

i > j の場合に加えて,さらに (1,..,1) という分割があるので dp[i-1][j] + 1 通り


あとはこれらに基づいて計算すればいい.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  static const int M = 1000000007;
  int n, m;
  cin >> n >> m;

  vector<vector<int> > dp(n, vector<int>(m, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 1;
      } else if (i == j) {
        dp[i][j] = (dp[i-1][j] + 1) % M;
      }
      else if (i < j) {
        dp[i][j] = (dp[i-1][j] + dp[i][j-i-1]) % M;
      } else {
        dp[i][j] = dp[i-1][j];
      }
    }
  }
  cout << dp[n-1][m-1] << endl;

  return 0;
}

が,これだと TLE するので dp を int dp[4500][4500] としてグローバルに宣言しておくことで TLE を回避できた.


一度アルゴリズムがわかってしまえばコードは簡単なので C でゴルフもしてみたところ,とりあえず 168B まで縮んだ.