土下座しながら探索中

主に競技プログラミング

SRM 730 easy : StonesOnATree

問題概要:
各頂点に重みのついた木が与えられる

.. 木の情報は以下の通り
.... 木の頂点数はnで表される
.... 木の各頂点には0からn-1までの番号が割り振られており、
.... i番目(0<=i<=n-1)の頂点の重みはw[i]で表される
.... また、各頂点の子の数は高々2である
この木を使ってゲームをする
ゲームで行える操作は次の2つ
1. どれか1つ石の置かれていない頂点を選び、石を置く
..ただし、石を置くには以下の制約を満たさなければならない
....石を置きたい頂点の全ての子供に石が置かれている
..石を置くと、重みにコストに足す
2. どれか1つ石の置かれている頂点を選び、その頂点から石を取り除く
..石を取り除くと、その頂点に石を置いたときに加算した重みをコストから引く
コストの初期値は0である
木の根に石を置くまでにかかったコストの最大値の最小値を求めよ

解説:
葉の部分から数えていく これは冗談でございます

解法の基本的な方針は次の通り
ある頂点に石を置いたら、その頂点の子の石は即座に取り除く、といった感じで葉から順に計算していく


もうすこししっかり書くと、
答えを求める関数をdfsとする
dfsは0以上n-1以下の整数iを受け取り、
そのiを根とする部分木について概要のゲームをといたときの答えを返す
このとき、dfsは次のように定義できる

BASIS :
.. Case : 頂点が葉のとき
頂点の番号をiとしたとき、答えは明らかにw[i]なのでw[i]を返す

INDUCTION:
.. Case : 頂点が1つしか子を持たないとき
今見ている頂点の番号をi,子の頂点の番号をjとすると
答えとなりうる値はw[i]+w[j]か頂点iに石を置くために必要なコストの最大値のどちらか
選択の余地はないので大きい方をかえす

.. Case : 頂点が2つ子を持つとき
答えとなりうる最大値は以下の4つのいずれか
左の子→右の子→今見ている頂点の順番で石を置いたときの最大値か
右の子→左の子→今見ている頂点の順番で石を置いたときの最大値か
左の子に石を置くために必要なコストの最大値か
右の子に石を置くために必要なコストの最大値か
これは選択できるので、もっとも小さい値を返す

コード:

const int IINF = INT_MAX;
#define MAX 20000
vector<int> G[MAX];
vector<int> w;
int V;

int dfs(int cur) {
  if( G[cur].size() == 0 ) {
    return w[cur];
  } if( G[cur].size() == 1 ) {
    return max(w[cur]+w[G[cur][0]],dfs(G[cur][0]));
  }
  assert( G[cur].size() == 2 );
  int ret = 0;
  int L = G[cur][0], R = G[cur][1];
  int Lmaxi = dfs(L), Rmaxi = dfs(R);
  ret = max(Lmaxi,Rmaxi);
  ret = max(ret,min(Lmaxi+w[R],Rmaxi+w[L]));
  ret = max(ret,w[cur]+w[L]+w[R]);
  return ret;
}

class StonesOnATree {
public:
  int minStones(vector <int> p, vector <int> _w) {
    V = _w.size();
    rep(i,V) w.push_back(_w[i]);
    rep(i,(int)p.size()) G[p[i]].push_back(i+1);
    return dfs(0);
  }
};