TopCoder SRM617 DIV1 MEDIUM - PieOrDolphin

Source

TopCoder SRM617 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

$50$ 人の人 $0,1,\ldots,49$ がいる．
$N$ 日間だけ，毎日その中の $2$ 人を選び，ミーティングを行った．各日で誰と誰を選んだかは与えられる．
ミーティングの際には，$1$ 人にはイルカのおもちゃを，$1$ 人にはパイのおもちゃを与える．
$N$ 日終了後の人 $k$ が持っているイルカのおもちゃとパイのおもちゃの数の差の絶対値を $d_k$ とする．
$d_k$ の和が最小になるような，各ミーティングでのおもちゃの配り方を $1$ つ求める問題．

解法

$d_k$ の和の最小値は，合計で奇数個だけのおもちゃをもらう人数に等しい．
これより小さくできないのは自明で，これを達成する配り方を見つければ文句はない．
ミーティングを行った人と人の間に枝を張ったグラフを考える．
その中で，毎ステップ，まだ配っていないミーティングに関する枝のみを通る極大のパスを見つけてくる．（同じノードを何回訪れても良い）
それは，始点を適当に決めて，DFSを $2$ 回（順方向，逆方向）してつなげてやれば良い．
そのパスにそって，$u$ から $v$ に向かう各枝 $(u,v)$ について，$u$ にイルカ，$v$ にパイなどとして配る．
パスの真ん中のノードたちは，同じ数だけのおもちゃをもらい，次数が偶数だけ減る．
パスの両端（始点と終点）は，もらうおもちゃの数が $1$ だけ変わり，$d_k$ の和に貢献してしまうが，こいつらからもう枝を伸ばせないことから，これらのノードの次数は $0$ になり，これらのノードの次数はもともと奇数であることがわかる．
両方向にDFSしなくても，次数が奇数のノードを優先的に始点に選んでDFSしても良い．

C++によるスパゲッティなソースコード

// #includeなどは略しています
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int used[1100];
int edge[51][1100], es[51], num[51][1100];
vector<int> res;

int dfs(int now, int fg){
  int i, j, k, ee;
  int r = 0;

  rep(k,es[now]){
    ee = num[now][k];
    if(ee < 0) ee = (-ee) - 1;
    else       ee = ee - 1;
    if(used[ee]) continue;

    i = edge[now][k];
    used[ee] = 1;
    res[ee] = 1;
    if(fg < 0) res[ee] = 3 - res[ee];
    if(num[now][k] < 0) res[ee] = 3 - res[ee];
    r += dfs(i, fg) + 1;
    break;
  }

  return r;
}

class PieOrDolphin {
public:
vector <int> Distribute(vector <int> A, vector <int> B) {
  int i, j, k, n;

  n = A.size();
  res.clear();
  rep(i,n) res.push_back(0);
  
  rep(i,50) es[i] = 0;
  rep(i,n) used[i] = 0;
  rep(i,n){
    edge[A[i]][es[A[i]]] = B[i];
    num[A[i]][es[A[i]]] = (i+1);
    es[A[i]]++;
    edge[B[i]][es[B[i]]] = A[i];
    num[B[i]][es[B[i]]] = -(i+1);
    es[B[i]]++;
  }

  int cnt = 0;
  rep(i,50){
    for(;;){
      k = 0;
      k += dfs(i, 1);
      if(k) cnt++;
      k += dfs(i, -1);
      if(k) cnt++;
      if(k==0) break;
    }
  }

  return res;
}

}

Current time: 2024年04月19日22時45分40秒
Last modified: 2014年04月22日13時20分03秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM617 SRM_Div1_Medium
トップページに戻る

Logged in as: unknown user (not login)

ログイン：