唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

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";
		}
	}

}