TopCoder SRM 522 Div 2

1074→1146．
250と550を解いてチャレンジ一つ成功．
相変わらず3つ目まで解けない．

250

http://community.topcoder.com/stat?c=problem_statement&pm=11582
矩形内に入る点の数を計算．
x座標でソート済み．
点の数が50なので，左端と右端を全探索しても50^3よりも小さいので，力任せで大丈夫．

ソースコード

public class PointErasingTwo {

	public int getMaximum(int[] y) {
		int L = y.length;
		if(L == 2){
			return 0;
		}
		int max = 0;
		for(int i = 0; i < L - 1; i++) {
			for(int j = i + 2; j < L; j++) {
				int sum = 0;
				for(int k = i; k < j; k++) {
					if((y[k] < y[i] && y[k] > y[j]) || y[k] > y[i] && y[k] < y[j]){
						sum++;
					}
				}
				max = Math.max(max, sum);
			}
		}
		return max;
	}

}

550

http://community.topcoder.com/stat?c=problem_statement&pm=11605
お互いに相手の陣地を消し合って最後に残っていたほうが勝ち．
連続した陣地は一度に消せる．
方針はAとBの区間の数をカウント．

Challenge Phaseに見たエレガントな別解．
状態は"A.*A"と"A.*B"と"B.*A"と"B.*B"しかなく，先頭と末尾だけで勝敗を判断できる．
もしも先頭がAならば，#A(Aの数)>=#BなのでAの勝ち．
先頭がBならば，末尾がAの時#A==#BでAの勝ち．末尾がBの時#A<#BとなりBの勝ち．

ソースコード

区間の数をカウントする方式．

public class RowAndManyCoins {

	public String getWinner(String cells) {
		int A = 0;
		int B = 0;
		char hist = ' ';
		for(char c : cells.toCharArray()) {
			if(c == hist) {
				continue;
			} else if(c == 'A') {
				A++;
			} else {
				B++;
			}
			hist = c;
		}
		if(A >= B) {
			return "Alice";
		} else {
			return "Bob";
		}
	}

}