糞問セットでDiv1昇格ｗ

昨日の結果

oo- +0/-0
65th(Room 2nd)
654.91pts

レートは・・・

じゃかじゃかじゃかじゃかじゃかじゃん（小並感）

1181 -> 1239(Highest)
Div.1昇格

やったねたえちゃん

f:id:touyou1121:20120902084336j:plain

でも昨日は糞問というか簡単な回だったので幸運なところもあったかも…
青組に忠誠をちゃんとちかえました！

TheBrickTowerEasyDivTwo

ちょっと頭使って数えるだけ
弾く条件のところで手間取ってしまって得点低かった

class TheBrickTowerEasyDivTwo {
public:
  int find( int redCount, int redHeight, int blueCount, int blueHeight ) {
	set<int> res;
	for (int i=0; i<=redCount; i++) {
	  for (int j=i+1; j<i+2&&j<=blueCount; j++) {
		res.insert(i*redHeight+j*blueHeight);
	  }
	  for (int j=i-1; j<=blueCount&&j>i-2&&j>=0; j--) {
		res.insert(i*redHeight+j*blueHeight);
	  }
	  if (i!=0&&i<=blueCount) res.insert(i*redHeight+i*blueHeight);
	  //printf("i=%d :%d\n",i,res.size());
	}
	return res.size();
  }
};

TheBrickTowerMediumDivTwo

問題のMedium。ブロックのタワーを一直線に並べたいんだけど、ドミノみたいにならないようにその間をお互いに干渉しない距離離す（ようするに左右どっちか高さが高い方の高さと同じだけ離す）として、全体の長さが最小になるものを求めよというやつ。
なんか見た目DPっぽくて、ある程度難しそうだなーとか一瞬思ったんだけど制約見たら…

タワーの数<=7
ふぁ！？

普通にやるだけやん、やばすぎ
まぁそういうわけで美味しく450点近くを手に入れました

class TheBrickTowerMediumDivTwo {
public:
  vector <int> find( vector <int> heights ) {
	vector<P> perm;
	int n = heights.size();
	for (int i=0; i<n; i++) {
	  perm.push_back(P(i,heights[i]));
	}
	sort(perm.begin(), perm.end());
	vector<int> res;
	int ans = INT_MAX;
	do {
	  int temp = 0;
	  for (int i=0; i<n-1; i++) {
		temp += max(perm[i].second, perm[i+1].second);
	  }
	  if (temp < ans) {
		res.resize(0);
		ans=temp;
		for (int i=0; i<n; i++) {
		  res.push_back(perm[i].first);
		}
	  }
	} while(next_permutation(perm.begin(), perm.end()));
	return res;
  }
};