TopCoder SRM 575 Div 2 ○○- 1070->1104

221th, +1/-1 challenge

250

配列中の任意の2箇所を入れ替えた時にできる配列の異なり数。
文字列化してsetに入れて数えただけ。

import java.util.HashSet;

public class TheSwapsDivTwo {

	public int find(int[] sequence) {
		HashSet<String> set = new HashSet<String>();
		int L = sequence.length;
		for(int i = 0; i < L; i++) {
			for(int j = i + 1; j < L; j++) {
				String temp = "";
				for(int k = 0; k < L; k++) {
					int cand = -1;
					if(k == i) {
						cand = sequence[j];
					} else if (k == j) {
						cand = sequence[i];
					} else {
						cand = sequence[k];
					}

					if(cand < 10) {
						temp += "0";
					}
					temp += Integer.toString(cand);
				}
				set.add(temp);
			}
		}

		return set.size();
	}

}

500

二人のプレイヤーが交互に、現在の数nからnの約数を引いていった時の勝者を答える。
蟻本でコインを取っていく話とかNimとかGrundy数とかを読んでいたのでそれ系かなーと思ったけどすぐには書けず。
結局DPで簡単に書けました

入力が1だと間違った答えを返す人がいたのでchallengeして成功。

import java.util.ArrayList;

public class TheNumberGameDivTwo {

	public String find(int n) {
		ArrayList<ArrayList<Integer>> divs = new ArrayList<ArrayList<Integer>>();
		for(int i = 0; i < 1001; i++) {
			divs.add(new ArrayList<Integer>());
		}
		for(int i = 2; i < 1001; i++) {
			for(int j = 2; j < 1001; j++) {
				if(i == j) {
					continue;
				}
				if(i % j == 0) {
					divs.get(i).add(j);
				}
			}
		}

		boolean win[] = new boolean[1001];
		win[0] = false;
		win[1] = false;
		for(int i = 2; i < 1001; i++) {
			win[i] = false;
			for(int x : divs.get(i)) {
				win[i] |= x <= i && !win[i - x];
			}
		}

		if(win[n]) {
			return "John";
		} else {
			return "Brus";
		}
	}

}

1000

チェス盤の駒が置かれていない部分にL字型のブロックを置いていく時に、置ける最大の個数を求める。
ただしL字ブロックの角の部分が黒いマス(i + jが偶数)になるようにする。
残り20分ぐらいしかなかったので、とりあえず左上から貪欲においていったら、案の定サンプルすら通らず。

public class TheTilesDivTwo {

	public int find(String[] board) {
		int L = board.length;
		int L2 = board[0].length();
		int state[][] = new int[L + 2][L2 + 2];
		for(int i = 0; i < L ; i++) {
			for(int j = 0; j < L2; j++) {
				if(board[i].charAt(j) == '.') {
					state[i + 1][j + 1] = 1;
				} else {
					state[i + 1][j + 1] = 0;
				}
			}
		}

		int count = 0;
		for(int i = 0; i < L ; i++) {
			for(int j = 0; j < L2; j++) {
				if((state[i + 1][j + 1] == 1) && (i + j) % 2 == 0) {
					if((state[i][j + 1] == 1) && (state[i + 1][j] == 1)) {
						state[i + 1][j + 1] = 2;
						state[i][j + 1] = 2;
						state[i + 1][j] = 2;
						count++;
					} else if((state[i][j + 1] == 1) && (state[i + 1][j + 2] == 1)) {
						state[i + 1][j + 1] = 2;
						state[i][j + 1] = 2;
						state[i + 1][j + 2] = 2;
						count++;
					} else if((state[i + 2][j + 1] == 1) && (state[i + 1][j] == 1)) {
						state[i + 1][j + 1] = 2;
						state[i + 2][j + 1] = 2;
						state[i + 1][j] = 2;
						count++;
					} else if((state[i + 2][j + 1] == 1) && (state[i + 1][j + 2] == 1)) {
						state[i + 1][j + 1] = 2;
						state[i + 2][j + 1] = 2;
						state[i + 1][j + 2] = 2;
						count++;
					}
				}
			}
		}
		return count;
	}

}