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

TopCoder SRM 538 Div1 Medium: TurtleSpy

競技プログラミング SRM

解法

右回転と左回転の中から上手く組み合わせてできるだけ180度に近い角度を作る。最初にできるだけまっすぐ進み、次に180度に出来るだけ近くなるように回転し、そこから反対向きにまっすぐ進み、最後にその場で消費しきれていない回転コマンドを使いきれば良い。

コード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class TurtleSpy {

	public double maxDistance(String[] commands) {
		int forward = 0;
		int backward = 0;
		ArrayList<Integer> right = new ArrayList<>();
		ArrayList<Integer> left = new ArrayList<>();
		for (String command : commands) {
			String[] tokens = command.split(" ");
			if (tokens[0].equals("left")) {
				left.add(Integer.parseInt(tokens[1]));
			} else if (tokens[0].equals("right")) {
				right.add(Integer.parseInt(tokens[1]));
			} else if (tokens[0].equals("forward")) {
				forward += Integer.parseInt(tokens[1]);
			} else if (tokens[0].equals("backward")) {
				backward += Integer.parseInt(tokens[1]);
			}
		}

		Collections.sort(left);
		Collections.sort(right);

		boolean[] checkLeft = dp(left);
		boolean[] checkRight = dp(right);
		int max = 0;
		for (int l = 0; l < checkLeft.length; l++) {
			for (int r = 0; r < checkRight.length; r++) {
				if (checkLeft[l] && checkRight[r]) {
					int deg = Math.abs(l - r);
					deg = Math.min(360 - deg, deg);
					max = Math.max(max, deg);
				}
			}
		}

		double y = Math.max(forward, backward) + Math.min(forward, backward)
				* Math.cos((double) Math.PI * (180.0 - max) / 180.0);
		double x = Math.min(forward, backward)
				* Math.sin((double) Math.PI * (180.0 - max) / 180.0);

		return Math.sqrt(x * x + y * y);
	}
	private boolean[] dp(ArrayList<Integer> list) {
		int N = 360;
		boolean[] check = new boolean[N];
		check[0] = true;
		for (int turn : list) {
			boolean[] nextCheck = Arrays.copyOf(check, N);
			for (int deg = 0; deg < N; deg++) {
				if (check[deg]) {
					int next = (deg + turn) % N;
					nextCheck[next] = true;
				}
			}
			check = nextCheck;
		}

		return check;
	}

}