TopCoder納め

1021->1024
全部一応解いたんですけど、MedとHardがおちましたorz

Medは完全不注意でしたね。はい。

MinCostPalindrome

回文に必要な最小のコストを求めるやるだけ問題

class MinCostPalindrome {
public:
   int getMinimum( string s, int oCost, int xCost ) {
	string rev=s;
	reverse(rev.begin(), rev.end());
	int res=0;
	for (int i=0; i<s.length(); i++) {
		if (s[i]=='?'&&rev[i]=='?') res+=min(oCost,xCost);
		else if (s[i]=='?'&&rev[i]=='o') res+=oCost;
		else if (s[i]=='?'&&rev[i]=='x') res+=xCost;
		else if (rev[i]!='?'&&s[i]!=rev[i]) return -1;
	}
	return res;
   }
};

Cut

不注意でした。
カットの回数制限内で10の個体をいくつ作れるかという問題。
10の倍数は最後にもう一個できるのでそれを優先させなきゃいけなかったのですが気付かずチャレンジで落とされました・・・

もう直すのは簡単で、さっき冬期講習から帰ってきて数分でなおしてAC

class Cut {
public:
	int getMaximum( vector <int> eelLengths, int maxCuts ) {
		int res=0;
		vector<int> teneel, other;
		for (int i=0; i<eelLengths.size(); i++) {
			if (eelLengths[i]%10==0) teneel.push_back(eelLengths[i]);
			else other.push_back(eelLengths[i]);
		}
		sort(teneel.begin(),teneel.end());
		for (int i=0; i<teneel.size(); i++) {
			if (maxCuts!=0) {
				while (teneel[i]>10) {
					teneel[i]-=10;
					res++; maxCuts--;
					if (maxCuts==0) break;
				}
			}
			if (teneel[i]==10) res++;
		}
		if (maxCuts!=0) {
			for (int i=0; i<other.size(); i++) {
				if (maxCuts!=0) {
					while (other[i]>10) {
						other[i]-=10;
						res++; maxCuts--;
						if (maxCuts==0) break;
					}
				}
			}
		}
		return res;
	}
};

Mosquitoes

それぞれの蚊二匹の組が一番近づく時間の中に多くの蚊が一点に集中する場所があると思い、O(n^3 log n)のコード書いたのですが、どうやら考え方が間違っていたのか落ちてました。

検討に時間がかかるのでまたの機会に・・・
間違えコード貼り

class Mosquitoes {
public:
	int getMaximum( vector <int> xInit, vector <int> v, int R ) {
		int sz=xInit.size();
		if (sz==1) return 1;
		pii mos[sz];
		for (int i=0; i<sz; i++) {
			mos[i].first=(double)xInit[i];
			mos[i].second=v[i];
		}
		set<double> prop;
		for (int i=0; i<sz; i++) {
			for (int j=0; j<sz; j++) if (i!=j) {
				if (mos[i].first<mos[j].first) {
					double dis=mos[j].first-mos[i].first;
					double V=mos[j].second*(-1)+mos[i].first;
					if (V>0) prop.insert(dis/V);
				} else {
					double dis=mos[i].first-mos[j].first;
					double V=mos[i].second*(-1)+mos[j].second;
					if (V>0) prop.insert(dis/V);
				}
			}
		}
		int res=0;
		for (set<double>::iterator it=prop.begin(); it!=prop.end(); it++) {
			double state[sz];
			for (int i=0; i<sz; i++) state[i]=mos[i].first+mos[i].second*(*it);
			sort(state, state+sz);
			for (int i=0; i<sz; i++)
				res=max(res,upper_bound(state,state+sz,state[i]+2*R)-state-i);
		}
		double state[sz];
		for (int i=0; i<sz; i++) state[i]=mos[i].first;
		sort(state,state+sz);
		for (int i=0; i<sz; i++)
			res=max(res,upper_bound(state,state+sz,state[i]+2*R)-state-i);
		return res;
	}
};