読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

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

TopCoder SRM 580 Div 2 ○-○ 1019->1127

34th, 0/0 challenge
前回Div 2 Hardが解けそうでしたが時間が足りなかったので、今回は最初にHardを開いたら初めてDiv 2 Hardが解けました。

Easy

範囲がかぶっているペアの数を答えるだけ。
焦っていて何故か範囲の比較の条件式が思いつかず、間の値を全部セットに入れて共通部分をとるというアレなことをしてしまった。

import java.util.HashSet;

public class ShoutterDiv2 {

	public int count(int[] s, int[] t) {
		int L = s.length;
		int count = 0;

		for(int i = 0; i < L; i++) {
			for(int j = i + 1; j < L; j++) {
				HashSet<Integer> x = new HashSet<Integer>();
				for(int k = s[i]; k < t[i] + 1; k++) {
					x.add(k);
				}
				HashSet<Integer> y = new HashSet<Integer>();
				for(int k = s[j]; k < t[j] + 1; k++) {
					y.add(k);
				}
				x.retainAll(y);
				if(x.size() > 0) {
					count += 1;
				}
			}
		}
 		return count;
	}

}

Hard

それぞれのマスにスコアが設定されている盤面が与えられる。
一番左上から、同じマスを2回通らずに、下と左右に移動できるときに、一番下の列に到達した時の最大の移動コストを答える
解法は動的計画法をやるだけ

後でよく考えたら問題を一部誤読していたような気がしますが通ったのでよかったです

public class WallGameDiv2 {

	public int play(String[] costs) {
		int L = costs.length;
		int L_in = costs[0].length();

		int c[][] = new int[L + 2][L_in + 2];

		for(int i = 0; i < L + 2; i++) {
			for(int j = 0; j < L_in + 2; j++) {
				c[i][j] = 1000000;
			}
		}

		for(int i = 0; i < L; i++) {
			for(int j = 0; j < L_in; j++) {
				if(costs[i].charAt(j) != 'x') {
					c[i + 1][j + 1] = costs[i].charAt(j) - '0';
				} else {
					c[i + 1][j + 1] = -1000000;
				}
			}
		}

		int down[][] = new int[L + 2][L_in + 2];
		for(int i = 1; i < L + 2; i++) {
			for(int j = 0; j < L_in + 2; j++) {
				down[i][j] = -1000000;
			}
		}
		int left[][] = new int[L + 2][L_in + 2];
		int right[][] = new int[L + 2][L_in + 2];
		for(int i = 0; i < L + 2; i++) {
			for(int j = 0; j < L_in + 2; j++) {
				left[i][j] = -1000000;
				right[i][j] = -1000000;
			}
		}

		for(int j = 1; j < L_in; j++) {
			down[0][j + 1] = -1000000;
		}
		for(int i = 0; i < L; i++) {
			for(int j = 0; j < L_in; j++) {
				if(down[i][j + 1] >= 0) {
					down[i + 1][j + 1] = down[i][j + 1] + c[i + 1][j + 1];
				} else {
					down[i + 1][j + 1] = -1000000;
				}
			}

			if(i < L - 1) {
				for(int j = 0; j < L_in; j++) {
					if(Math.max(down[i + 1][j + 1], right[i + 1][j + 1]) >= 0) {
						right[i + 1][j + 2] = Math.max(down[i + 1][j + 1], right[i + 1][j + 1]) + c[i + 1][j + 2];
					} else {
						right[i + 1][j + 2] = -1000000;
					}
				}

				for(int j = L_in - 1; j >= 0; j--) {
					if(Math.max(down[i + 1][j + 1], left[i + 1][j + 1]) >= 0) {
						left[i + 1][j] = Math.max(down[i + 1][j + 1], left[i + 1][j + 1]) + c[i + 1][j];
					} else {
						left[i + 1][j] = -1000000;
					}
				}

				for(int j = 0; j < L_in; j++) {
					down[i + 1][j + 1] = Math.max(Math.max(down[i + 1][j + 1], right[i + 1][j + 1]), left[i + 1][j + 1]);
				}
			}
		}

		int max = -1;
		for(int j = 0; j < L_in; j++) {
			max = Math.max(max, down[L][j + 1]);
		}

		return max;
	}

}
-->