TopCoder SRM 538(2012/03/21)

メモ

EvenRoute

ある点とある点の経路長のパリティは経路によらないため，各点を最終訪問点とした時のパリティを計算すれば良い．

public class EvenRoute{
	public String isItPossible(int[] x, int[] y, int par){
		int n=x.length;
		boolean ok=false;
		for(int i=0; i<n; i++){
			ok|=(abs(x[i]+y[i])%2)==par;
		}
		return ok?"CAN":"CANNOT";
	}
}

TurtleSpy

回転->前進->回転->後進
最適な動きは↑のパターンしかない．従って，2回目の回転角度は，後進した時に損が最小となるものを求めれば良い．角度が整数なので，実現できる角度全てを求め，全パターン計算する事が出来る．

public class TurtleSpy{
	public double maxDistance(String[] ss){
		int forward=0, backward=0;
		ArrayList<Integer> degrees=new ArrayList<Integer>();
		for(String s : ss){
			Scanner sc=new Scanner(s);
			String com=sc.next();
			int val=sc.nextInt();
			if(com.equals("right")){
				degrees.add(val);
			}else if(com.equals("left")){
				degrees.add(-val);
			}else if(com.equals("forward")){
				forward+=val;
			}else{
				backward+=val;
			}
		}
		int n=degrees.size();
		boolean[][] dp=new boolean[n+1][360];
		dp[0][0]=true;
		for(int j=0; j<n; j++){
			for(int i=0; i<360; i++){
				int degree=i+degrees.get(j);
				degree=(degree+360)%360;
				dp[j+1][degree]|=dp[j][i];
				dp[j+1][i]|=dp[j][i];
			}
		}
		double max=0;
		for(int i=0; i<360; i++){
			if(dp[n][i]){
				max=max(max, calc(i, forward, backward));
				max=max(max, calc(i, backward, forward));
			}
		}
		return max;
	}

	double calc(int deg, int d1, int d2){
		double x=0, y=0;
		x+=d1*cos(0);
		y+=d1*sin(0);
		x-=d2*cos(toRadians(deg));
		y-=d2*sin(toRadians(deg));
		return sqrt(x*x+y*y);
	}
}

Result

oo- +0/-0 396.6pts. 236th
1816 -> 1832

Slow Coder．