TopCoder SRM 528 Div 2

1167→1172．青コーダーへの道は遠い……．
Easyを解いてMediumはシステムテストで落とされる．チャレンジ5つ成功1つ失敗．

Easy

文字列が回文にするための最小のコストを求める．
端っこから真ん中まで1つずつ確かめていくだけ．

public class MinCostPalindrome {

	public int getMinimum(String s, int oCost, int xCost) {
		int len = s.length();
		int min = Math.min(oCost, xCost);
		int sum = 0;
		for(int i = 0; i < len / 2; i++) {
			if(s.charAt(i) == s.charAt(len - 1 - i) && s.charAt(i) == '?') {
				sum += min * 2;
			}
			if((s.charAt(i) == 'x' && s.charAt(len - 1 - i) == 'o') || (s.charAt(i) == 'o' && s.charAt(len - 1 - i) == 'x')) {
				return -1;
			}
			if((s.charAt(i) == 'x' && s.charAt(len - 1 - i) == '?') || (s.charAt(i) == '?' && s.charAt(len - 1 - i) == 'x')) {
				sum += xCost;
			}
			if((s.charAt(i) == 'o' && s.charAt(len - 1 - i) == '?') || (s.charAt(i) == '?' && s.charAt(len - 1 - i) == 'o')) {
				sum += oCost;
			}
		}
		return sum;
	}

}

Medium

長さがちょうど10のうなぎしか食べられないので，与えられた切断回数で最も多く食べられるうなぎの数を答える．
最初に10で割り切れるうなぎをやらないとダメ．20は1回切ると10+10になる

5人撃墜したけど，自分もSystem Testで死亡．

import java.util.Arrays;

public class Cut {

	public int getMaximum(int[] eelLengths, int maxCuts) {
		int len = eelLengths.length;
		int sum = 0;
		int count = 0;
		for(int i = 1; i < len; i++) {
			if((eelLengths[i] % 10 == 0)) {
				int temp = eelLengths[count];
				eelLengths[count] = eelLengths[i];
				eelLengths[i] = temp;
				count++;
			}
		}
		Arrays.sort(eelLengths, 0, count);
		for(int i = 0; i < len; i++) {
			if(eelLengths[i] == 10) {
				sum += 1;
			} else if(eelLengths[i] > 10 && maxCuts > 0) {
				while(eelLengths[i] > 10 && maxCuts > 0) {
					sum++;
					eelLengths[i] -= 10;
					maxCuts--;
				}
				if(eelLengths[i] == 10) {
					sum++;
				}
			}
		}
		return sum;
	}

}

Hard

蚊の初期位置と移動速度が与えられ，半径Rの爆弾で殺せる最大の数を求める．
任意の２つの蚊を選べばその蚊の間の距離が2Rになる時間tが計算できる．
tがわかれば2Rの範囲内にある蚊の数を求めるのは簡単なので，すべての組み合わせに対して時間tを求めれば良い．

ちゃんと動かず．

import java.util.Arrays;

public class Mosquitoes {

	public int getMaximum(int[] xInit, int[] v, int R) {
		int len = xInit.length;
		if(len == 1) {
			return 1;
		}
		double [] temp = new double[len];


		int max = 1;
		for(int j = 0; j < len; j++) {
			for(int k = 0; k < len; k++) {
				if(j == k) {
					continue;
				}
				if(true) {
					double t = ((double)2*R + xInit[j] - xInit[k]) / (v[k] - v[j]);
					if(t >= 0) {
						System.out.println("j: " + j + ", k: " + k + ", t: " + t);
						for(int i = 0; i < len; i++) {
							temp[i] = xInit[i] + v[i] * t;
						}
						Arrays.sort(temp);
						int head = 0;
						int tail = 0;
						while(head < len && tail < len - 1) {
							if(Math.abs(temp[head] - temp[tail + 1]) <= 2*R) {
								tail++;
								max = Math.max(tail - head + 1, max);
							} else {
								head++;
							}
						}
					}

					t = ((double)-2*R + xInit[j] - xInit[k]) / (v[k] - v[j]);
					if(t >= 0) {
						System.out.println(t);
						for(int i = 0; i < len; i++) {
							temp[i] = xInit[i] + v[i] * t;
						}
						Arrays.sort(temp);
						int head = 0;
						int tail = 0;
						while(head < len && tail < len - 1) {
							if(Math.abs(temp[head] - temp[tail + 1]) <= 2*R) {
								tail++;
								max = Math.max(tail - head + 1, max);
							} else {
								head++;
							}
						}
					}
				}
			}
		}


		return max;
	}

}