Hatena::Grouptopcoder

hoshi524の日記

2012-03-22SRM 538 DIV 1

450pt TurtleSpy

18:55

問題

TopCoder Statistics - Problem Statement

考えたこと

基本方針は分かったけど、角度で詰まった。

基本方針は最大距離を考える時、forward、backwardはそれぞれ足しあわせてforwardとbackwardが同じ方向になれば最大になる。

つまり、コマンドの選択としては

forwardを全て選択→ちょうど180度になるように角度を選択→backwardを全て選択→残りの角度を選択

という流れになる。

ちょうど180度になるような組み合わせがあるか、なければ1番近いものを選択する必要があるんだけど、うまい実装が思いつかず正当している方のコードを拝見したところ、bool[360]を用意して前の角度集合で作成できる角度+新しい角度みたいにやっていたので学習。

弧度法→ラジアンも記憶してないし、で本番では解けないだろうな。


returnのf*f+b*b-2*f*b*cos

x=f-b*cos

y=b*sin

x^2=f^2+b^2*cos^2-2*f*b*cos

y^2=b^2*sin^2

x^2+y^2=f^2+b^2*(sin^2+cos^2)-2*f*b*cos

sin^2+cos^2=1

x^2+y^2=f^2+b^2-2*f*b*cos

コード

public class TurtleSpy {
	public double maxDistance(String[] commands) {
		double b=0,f=0;
		boolean ok[]=new boolean[360];
		ok[0]=true;
		for(String str : commands){
			String sp[]=str.split(" ");
			int v=Integer.parseInt(sp[1]);
			if(sp[0].equals("forward")){
				f+=v;
			}else if(sp[0].equals("backward")){
				b+=v;
			}else if(sp[0].equals("left")){
				boolean tmp[]=new boolean[360];
				for(int i=0;i<360;i++){
					if(ok[i]){
						tmp[i]=true;
						tmp[(i+v)%360]=true;
					}
				}
				ok=tmp;
			}else if(sp[0].equals("right")){
				boolean tmp[]=new boolean[360];
				for(int i=0;i<360;i++){
					if(ok[i]){
						tmp[i]=true;
						tmp[(i-v+360)%360]=true;
					}
				}
				ok=tmp;
			}
		}
		double best=0;
		for(int i=0;i<=180;i++){
			if(ok[180-i] || ok[180+i]){
				best=(180-i)*Math.PI/180;
				break;
			}
		}
		return Math.sqrt(f*f+b*b-2*f*b*Math.cos(best));
	}
}