tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

SRM 492 Div1

どうにもならない。double嫌い。
250:なにか
doubleの誤差を回避する問題。方針は立つけどソースは書けない。doubleは嫌い(Practiceでもdoubleゲーはめったに通らない。)
通らないソースコード

>>
public class TimeTravellingGardener{
	public int determineUsage(int[] a,int[]b){
		int ret=99999999;
		int d[]=new int[b.length];
		d[0]=0;
		for(int i=1;i<b.length;i++){
			d[i]=d[i-1]+a[i-1];
		}
		for(int i=0;i<b.length;i++){
			for(int j=i+1;j<b.length;j++){
				double r=(double)(b[j]-b[i])/(double)(d[j]-d[i]);
				double start=(double)b[i]-r*(d[i]);
				int count=0;
				boolean ok=true;
				for(int k=0;k<b.length;k++){
					if(start+(double)d[k]*r+0.000001<(double)b[k])count++;
					if(start+(double)d[k]*r>(double)b[k])ok=false;
					if(start+(double)d[k]*r+0.000001<0)ok=false;
					//System.out.println(start+(double)d[k]*r);
				}
				if(ok)ret=Math.min(ret,count);
			}
		}
		for(int j=1;j<b.length;j++){
				double r=(double)(b[j])/(double)(d[j]);
				double start=0;
				int count=0;
				boolean ok=true;
				for(int k=0;k<b.length;k++){
					if(start+(double)d[k]*r+0.000001<(double)b[k])count++;
					if(start+(double)d[k]*r>(double)b[k])ok=false;
					if(start+(double)d[k]*r+0.0000001<0)ok=false;
				}
				if(ok)ret=Math.min(ret,count);
		}
		for(int j=0;j<b.length-1;j++){
				double r=(double)(-b[j])/(double)(d[j]);
				double start=(double)b[j]*(d[a.length])/(d[a.length]-d[j]);
				int count=0;
				boolean ok=true;
				for(int k=0;k<b.length;k++){
					if(start+(double)d[k]*r+0.000001<(double)b[k])count++;
					if(start+(double)d[k]*r>(double)b[k])ok=false;
					if(start+(double)d[k]*r+0.000001<0)ok=false;
				}
				if(ok)ret=Math.min(ret,count);
		}
		return ret;
	}
}
<<

550:なにか
しらない。と思ったらDPだった…… いいからちゃんとYahoo翻訳動け

1000:なにか
しらない

Challenge Phase
Div1に上がってから何もできてない。はやくDiv2いきたいくらい

System Test
通るわけがない。

Result
xxx
0 + 0 + 0 + 0 = 0
最下位より下
Rating
1513 -> 1429

またはいいろ……

double嫌い。次はintとlongだけ使う問題をお願いします。
どうせまたPracticeしてます。