SRM316 div2

easy
簡単すぎて申し訳ない．

  string getMessage(string text) {
    string ans = "";
    istringstream iss(text);
    string tmp;
    while(iss >> tmp) {
      ans += tmp[0];
    }
    return ans;
  }

medium
問題把握に時間かかり過ぎ．

  int fewestClicks(string messages, int low, int high) {
    int sz = messages.size();
    int mini = INF;
    for(int k = low; k <= high; k++) {
      int tmp = (int)((sz-0.5)/k); //in advance add "advance" operation number
      for(int i = 0; i < (sz-0.5)/k; i++) {
//whatever int k is ,never do err exception of out_of_range.
	string str = messages.substr(i*k, k);
	int cnt = count(str.begin(), str.end(), 'D');
	int inc = min(cnt, 1+(int)str.length()-cnt);
	tmp += inc;
	if(inc) tmp++;
      }
      mini = min(mini, tmp);
    }
    return mini;
  }

difficult
あれ、かんたん？ようするに、深さがどれだけかわかればいいんじゃない？
と思ってキューで組んだら問題の読み間違いで違うかった．やっぱり再帰は難しい．
おそらく、いつも、

ans+=dfs(node);

ってしてるからすごく時間がかかったのだと思う．反省．
要するに時間のかかりそうなノードから先に伝達しちゃいましょうという問題．スタックを使うのは想像に難くない．
再帰関数使えばいいわけね。

class SpreadingNews {
private:
  vector<int> arr[51];
  int dfs(int node);
public:
  int minTime(vector <int> supervisors) {
    int sz = supervisors.size();
    //子孫ノードを格納
    for(int i = 1; i < sz; i++) {
      arr[ supervisors[i] ].push_back(i);
    }
    return dfs(0);
       
  }
};

int SpreadingNews::dfs(int node) {
  vector<int> tmp = arr[node];
  int sz = tmp.size();
  vector<int> cost;
  if(sz == 0) return 0;
  //※
  for(int i = 0; i < sz; i++) {
    int c = dfs(tmp[i]);　//int c += dfs(tmp[i])とかしなくてよい。
/*int c = 0;
    c += dfs(tmp[i]);*/ //と同値．
    cost.push_back(c);
  }
  sort(cost.rbegin(), cost.rend());

//微妙に行き当たりばったり法.ここで順番も含めたnodeのコストが確定する．
  for(int i = 0; i < cost.size(); i++) {
    cost[i] += (i+1);
  }
  return *max_element(cost.begin(), cost.end() );
}

//※最初からこうしておけば話は早い．
  if(sz == 0) return 0;
  for(int i = 0; i < sz; i++) {
    cost.push_back(tmp[i]);
  }