Hatena::Grouptopcoder

hoshi524の日記

2012-04-16

SRM 540 DIV 1

18:24

250pt ImportantSequence

問題

TopCoder Statistics - Problem Statement

考えたこと

正直さっぱりわからなかった。

同様の問題がでても解ける気があまりしないけど、とりあえず解法がなんとなく分かったので書き残す。

最初の数を決めると、あとの数は一意に決まるため全部試すことは簡単だけど数が多くて駄目。

加減しかつかってないため、成立する最初の数が連続になるため、その範囲を求めることで成立するケースの数が求まる。

最初の条件は、例えば

a+b=3 (b>=1)

から、a>=2であることが簡単に分かるが、以降の条件は前の条件を加味していく必要がある。

そこで、例えば入力が

{2,4,3}
"-++"

の時

a-b=2 (b>=1)
b+c=4 (c>=1)
c+d=3 (d>=1)

となり、これを整理すると

a      - (a-2)  = 2 ((a-2) >=1)
(a-2)  + (-a+6) = 4 ((-a+6)>=1)
(-a+6) + (a-3)  = 3 ((a-3) >=1)

となり、条件から

(a-2)  >=1 → a>=3
(-a+6) >=1 → a<=5
(a-3)  >=1 → a>=4

であることが分かり、a=最初の数の範囲が分かる

コード


public class ImportantSequence {
	public int getCount(int[] B, String operators) {
		boolean k=true;
		long b=0,left=1,right=Long.MAX_VALUE,n=B.length;
		for(int i=0;i<n;i++){
			if(operators.charAt(i)=='+'){
				k=!k;
				b=B[i]-b;
			}else{
				b=b-B[i];
			}
			if(k){
				left=Math.max(left, 1-b);
			}else{
				right=Math.min(right, b-1);
			}
		}
		if(left<=right){
			if(right==Long.MAX_VALUE)
				return -1;
			else
				return (int)(right-left+1);
		}else
			return 0;
	}
}

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