Hatena::Grouptopcoder

hoshi524の日記

2012-03-22SRM 538 DIV 1

250pt EvenRoute

18:55

問題

TopCoder Statistics - Problem Statement

考えたこと

偶奇しか問われてなかったので、探索は一切考えなかった。(x+y)&1でstepが偶数奇数かはすぐ分かるし。

結果的にはこれが良かったが、安全な思考だった気はしない。勘でやった。

どこから行っても良い事を理解してなくて、最初から順に行って調べたらexample2で失敗した。

example2は最小ケースになっていて、ここから偶数の位置、奇数の位置を足したりした。

偶数奇数の状態遷移図で考えると単純な構造になっていて、偶数の位置がいくつあろうが奇数の位置が1つあれば"CAN"だし、逆も然りだった。

コード

public class EvenRoute {
	public String isItPossible(int[] x, int[] y, int wantedParity) {
		int n=x.length;
		boolean kisu=false,guu=false;
		for(int i=0;i<n;i++){
			if((x[i]+y[i])%2==0){
				guu=true;
			}else{
				kisu=true;
			}
		}
		if(wantedParity==1){
			return kisu?"CAN":"CANNOT";
		}else{
			return guu?"CAN":"CANNOT";
		}
	}
}

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));
	}
}