TopCoder SRM 525 Div 2

1146→1167．
Smallを解いてチャレンジ一つ成功一つ失敗．
10分ぐらいでSmallが解けて，調子がいいなと思ったらMediumで爆死．
プログラムを書き終わったと思ったら何故かサンプルインプットの最後が通らず．

Small

スタートからゴールまでいけるか判定する問題．縦一列が埋まってるかどうか確かめるだけ．

public class RainyRoad {

	public String isReachable(String[] road) {
		int L = road[0].length();
		for(int i = 0; i < L; i++) {
			int c = 0;
			for(int j = 0; j < 2; j++) {
				if(road[j].charAt(i) == 'W') {
					c++;
				}
			}
			if(c >= 2) {
				return "NO";
			}
		}
		return "YES";
	}

}

Medium

ボードを上下左右に動かして，端からはみ出したボードの上に乗っているコインを落として，規定の枚数になるまでの最低の回数を求める．

動かない．愚直な実装．
Challenge Phaseの時に他人のコードを見て，矩形を選択する問題だと気づいたけど後の祭り．

import java.util.Comparator;

public class DropCoins {

	private class Comp implements Comparator<Comp> {
		public int[][] state = null;
		public int coin = 0;
		public Comp(int[][] state) {
			super();
			this.state = new int[state.length][state[0].length];

			for(int i = 0; i < state.length; i++) {
				for(int j = 0; j < state[0].length;j++) {
					this.state[i][j] = state[i][j];
				}
			}
			count();
		}
		private void count() {
			int c = 0;
			for(int[] str: state) {
				for(int ch: str) {
					c += ch;
				}
			}
			coin = c;
		}
		public void up() {
			int c = 0;
			for(int i = 0; i < state[0].length; i++) {
				c += state[0][i];
			}
			for(int i = 0; i < state.length - 1; i++) {
				for(int j = 0; j < state[0].length;j++) {
					state[i][j] = state[i + 1][j];
				}
			}
			for(int j = 0; j < state[0].length;j++) {
				state[state.length - 1][j] = 0;
			}
			coin -= c;
		}
		public void down() {
			int c = 0;
			for(int i = 0; i < state[0].length; i++) {
				c += state[state.length - 1][i];
			}
			for(int i = state.length - 1; i >= 1; i--) {
				for(int j = 0; j < state[0].length;j++) {
					state[i][j] = state[i - 1][j];
				}
			}
			for(int j = 0; j < state[0].length; j++) {
				state[0][j] = 0;
			}
			coin -= c;
		}
		public void left() {
			int c = 0;
			for(int i = 0; i < state.length; i++) {
				c += state[i][0];
			}
			for(int i = 0; i < state.length; i++) {
				for(int j = 0; j < state[0].length - 1;j++) {
					state[i][j] = state[i][j + 1];
				}
			}
			for(int j = 0; j < state.length;j++) {
				state[j][state[0].length - 1] = 0;
			}
			coin -= c;
		}

		public void right() {
			int c = 0;
			for(int i = 0; i < state.length; i++) {
				c += state[i][state[0].length - 1];
			}
			for(int i = 0; i < state.length; i++) {
				for(int j = state[0].length - 1; j >= 1 ;j--) {
					state[i][j] = state[i][j - 1];
				}
			}
			for(int j = 0; j < state.length;j++) {
				state[j][0] = 0;
			}
			coin -= c;
		}
		public int compare(Comp o1, Comp o2) {
			return o1.coin - o2.coin;
		}
	}
	public int getMinimum(String[] board, int K) {
		int[][] arr = new int[board.length][board[0].length()];
		for(int i = 0; i < board.length; i++) {
			for(int j = 0; j < board[0].length(); j++) {
				if(board[i].charAt(j) == 'o') {
					arr[i][j] = 1;
				} else {
					arr[i][j] = 0;
				}
			}
		}
		int ret = 10000;
//		Comp x = new Comp(arr);
//		System.out.println(x.coin);
		for(int a = 0; a < board.length * 2.5 + 1; a++) {
			for(int b = 0; b < board.length * 2.5 + 1; b++) {
				for(int c = 0; c < board[0].length() * 2.5 + 1; c++) {
					for(int d = 0; d < board[0].length() * 2.5 + 1; d++) {
						Comp z = new Comp(arr);
						if(a + b + c + d >= ret) continue;
						for(int q1 = 0; q1 < a; q1++) {
							z.up();
						}
						for(int q1 = 0; q1 < b; q1++) {
							z.down();
						}
						for(int q1 = 0; q1 < c; q1++) {
							z.left();
						}
						for(int q1 = 0; q1 < d; q1++) {
							z.right();
						}
		//				if(K ==58)
		//				System.out.println(z.coin + ", " + a + ", " + b);
						if(z.coin == K) {
							System.out.println(a + ", " + b + ", " + c + ", " + d);
							return a + b + c + d;
						}
						/*
						for(int i = 0; i < board.length; i++) {
							for(int j = 0; j < board[0].length(); j++) {

								if(K ==12)
								System.out.print(z.state[i][j]);
							}

							if(K ==12)
							System.out.println();
						}
						*/
					}
				}
			}
		}
		if(ret == 10000) {
			return -1;
		} else {
			return ret;
		}
	}

}