SRM314 div2

easy

//計算量を下げるなら、vector<pii>とかで格納しておくのがよい。普通にやると、4じゅうるーぷとかなった、
  int dissatisfaction(vector <string> farmland) {
    int row = farmland.size();
    int col = farmland[0].length();
    vector<pii> dots;
    for(int i = 0; i < row; i++) {
      for(int j = 0; j < col; j++) {
	if(farmland[i][j] == 'C') {
	  dots.push_back(pii(i, j));
	}
      }
    }
    int mini = INF;
    for(int i = 0; i < dots.size(); i++) {
      int tmp = 0;
      int x = dots[i].X; int y = dots[i].Y;
      for(int j = 0; j < dots.size(); j++) {
	int nx = dots[j].X; int ny = dots[j].Y;
	tmp += (nx-x)*(nx-x)+(ny-y)*(ny-y);
      }
      mini = min(tmp, mini);
    }
    return mini;

medium
はじめてリスト使ったわ．おそらくこれが最速。left.size() <= 10なのでpermutationつかってもいいけど、こっちのほうが精神衛生上？いいと判断．

class StandInLine {
public:
  vector <int> reconstruct(vector <int> left) {
    list<int> order;
    list<int>::iterator it;
    int sz = left.size();
    for(int i = sz-1; i >= 0; i--) {
      int cnt = 0; 
//リストは[]演算子と-演算子を使えない．
      for(it = order.begin(); it != order.end(); it++) {
	if(cnt == left[i]) break;
	if(i+1 < *it) cnt++;
      }
      
      order.insert(it, i+1);
    }
    return vector<int>(order.begin(), order.end() );
				   
  }

difficult
作りうる最大の三角形の面積を求めなさいというもの。
とりあえず、大きい辺からできうる三角形をひたすらつくったらいいんだろ、とか思ってたら2)の4 4 4 7でひっかかった。
[4, 4, 4]-->6.92.. [7, 4, 4]-->6.75.. でアウトになる．
大筋は合ってるから、dp使えばいいのかなと思ったらうまくいった．意外と簡単．
多分問題なす．

class GrasslandFencer {
private:
  double solveTriangleArea(int a, int b, int c);
public:
  double maximalFencedArea(vector <int> fences) {
    int sz = fences.size();
    sort(fences.begin(), fences.end());
    double dp[sz+1];
    memset(dp, 0, sizeof dp);
    for(int i = 2; i < sz; i++) {
      dp[i+1] = max(dp[i-2]+solveTriangleArea(fences[i], fences[i-1], fences[i-2]), dp[i]);
    }
    return dp[sz];
  }
    
};
//premises a > b > c
double GrasslandFencer::solveTriangleArea(int a, int b, int c) {
  if(a < b+c) {
    double p = (a+b+c)*1.0/2;
    return sqrt(p*(p-a)*(p-b)*(p-c) );
  }
  return 0.0;
}

他の人のソース見たけど、２重、３重ループしてる．
ちょっと考察．
area = sqrt(p*(p-a)*(p-b)*(p-c) )
a:固定．a = 4とする。
[4, 4, 4] > 
[4, 4, 3] >
[4, 4, 2] >
..

[4, 4, 4] >
[4, 3, 3] >
[4, 3, 2] >
...
てな感じになるはずだよね。
面積としては、
で、[4, 4, 4] > [4, 4, 3] > [4, 3, 3] > [4, 3, 2] 以下存在しない．
みたいになるはず．
それなら、b,cをできる限り大きいものにすると、面積は最大になるはず。
え..あってるよね..a = 7とかでもおなじ。