TopCoder SRM 528 Div2

805→905
この調子で上がってくれると嬉しい。

250

文字列が与えられる。
'?'を'x'に変えるのにはxCost、
'o'に変えるのにはoCostかかる。

与えられた文字列を回文にするのに必要なコストはいくらか。
ただし、回文にならないときは、-1を返せ。

やるだけ。でも実装が頭良くなかった。
Scala触ってると、引数のデータを変更するっていうのが思いつかなくなったりするんだよなぁ。。。

500

N匹のうなぎの長さが与えられる。
maxCuts回だけ切ることができるが、ちょうど長さ10のうなぎをいくつ作れるか。

10の倍数に気をつける。{10, 20, 30} 1 でかなり落ちるらしい。
撃墜されるのが怖かったので、かなり冗長に書いたつもり。

コード

• 250

struct MinCostPalindrome {
	int getMinimum(string s, int oCost, int xCost) {
		string left = s.substr(0, s.length() / 2);
		string right = s.substr(s.length() / 2);
		reverse(all(right));
		int ret = 0;
		for(int i = 0; i < (int)left.length(); i++) {
			char l = left[i];
			char r = right[i];
			if(l == '?' && r == 'o') {ret += oCost; left[i] = 'o';}
			else if(l == '?' && r == 'x') {ret += xCost; left[i] = 'x';}
			else if(l == '?' && r == '?') {ret += 2 * min(oCost, xCost);}
			else if(l == 'o' && r == '?') {ret += oCost; right[i] = 'o';}
			else if(l == 'x' && r == '?') {ret += xCost; right[i] = 'x';}
		}
		if(left != right) return -1;
		else return ret;
	}
};

• 250

struct Cut {
	int getMaximum(vector <int> eelLengths, int maxCuts) {
		typedef vector<int> vint;
		int tens = 0;
		vint times;
		vint others;
		each(it, eelLengths) {
			if(*it == 10) {
				tens++;
			}
			else if(*it % 10 == 0) {
				times.pb(*it);
			}
			else if(*it > 10) {
				others.pb(*it);
			}
		}
		int ret = tens;

		sort(all(times));
		for(int i = 0; i < (int)times.size() && maxCuts; i++) {
			if(times[i] / 10  - 1 <= maxCuts) {
				ret += times[i] / 10;
				maxCuts -= (times[i] / 10 - 1);
			} else {
				ret += maxCuts;
				maxCuts = 0;
			}
		}

		each(it, others) {
			if(*it / 10 <= maxCuts) {
				ret += *it / 10;
				maxCuts -= *it / 10;
			} else {
				ret += maxCuts;
				maxCuts = 0;
				break;
			}
		}

		return ret;
	}
};