TopCoder SRM 587 Div 2 xoo 1119->1180

250: InsertZ

ある文字列からzを取り除いたものが別の文字列と一致するかどうかを確かめるだけの問題のはずなのだが、なぜか間違えていて撃墜された

500: JumpFurther

1からNまでの数字それぞれについて総和に足していくか足さないかを選べる。
途中である数badStepになってはいけないという条件のもとで最大の和を求める。

解法は、とりあえず全部足してbadStepになるときは1引けばいいみたい。
ちなみに私は1からNまでのどれか一つを除いた総和で条件を満たすものの最大値を取ったが、これでも十分間に合う

public class JumpFurther {

	public int furthest(int N, int badStep) {
		int result = 0;

		int temp = 0;
		for(int i = 1; i <= N; i++) {
			temp += i;
			if(temp == badStep) {
				break;
			}
			if(i == N) {
				result = Math.max(result, temp);
			}
		}

		for(int skip = 1; skip <= N; skip++) {
			temp = 0;
			for(int i = 1; i <= N; i++) {
				if(i == skip) {
					continue;
				}
				temp += i;
				if(temp == badStep) {
					break;
				}
				if(i == N) {
					result = Math.max(result, temp);
				}
			}
		}

		return result;
	}

}

1000: ThreeColorabilityEasy

四角形の格子があって、それぞれの四角について左上から右下、あるいは右上から左下の斜めの辺が付いている(リンク先の図を見たほうが速い
それぞれの辺につながっているノードが別々の色になるように色分けしていく時、最後まで色塗り可能かどうか答える

縦2マス×横2マスの計4マスのうちある種類のマスが奇数個あるとうまくいかないので、あとはそれを確認するだけ

public class ThreeColorabilityEasy {

	public String isColorable(String[] cells) {
		if((cells.length == 1) || (cells[0].length() == 1)) {
			return "Yes";
		}
		int W = cells.length;
		int H = cells[0].length();

		int dx[] = {0, 0, 1, 1};
		int dy[] = {0, 1, 0, 1};
		for(int i = 0; i < W - 1; i++) {
			for(int j = 0; j < H - 1; j++) {
				int count = 0;
				for(int k = 0; k < 4; k++) {
					if(cells[i + dx[k]].charAt(j + dy[k]) == 'Z') {
						count++;
					}
				}
				if((count == 1) || (count == 3)) {
					return "No";
				}
			}
		}

		return "Yes";
	}

}