Google Code Jam Round2

出てました

Problem A.

歩道の遅いとこから走って行った方が早くなるから・・・
ソートとかしてやるだけじゃん
→なんか合わない
小数の精度とかいろいろ変える
→やっぱり合わない
40分も使って4WrongTryしたあげく諦める

Problem B.

もうなんかすごい焦ってる　英語もよく分かんない
とりあえずSmall通そう
超汚いコードだけど通った！
なんか累積和という言葉が脳裏をよぎる（JOI本選のトラウマ）
あ、累積和じゃん　それも2次元の（JOI（ry）
汚いコードだけどゴリゴリ実装
SmallのCorrectな解答と同じのが出たのでLarge提出

Problem A.に戻る

一つ型をintからdoubleに直したら通った
Small、LargeをSubmit

BのLargeが落ちて26点。WrongTriesも響いて1509位
限りなく不参加に近い最下位
次はRound3行きたいですね(野望

解答

Problem A

int main(){
	FILE* fp=fopen("out.txt","w");
	int t;scanf("%d",&t);
	REP(setn,t){
		int x,s,r,tt,n;scanf("%d%d%d%d%d",&x,&s,&r,&tt,&n);
		ld t=tt;
		int sum=0;
		vector<pair<ld,ld> > walk;//ここの変数をintにしてた
		REP(i,n){
			int b,e,w;scanf("%d%d%d",&b,&e,&w);
			sum+=e-b;
			walk.pb(mp(w,e-b));
		}
		sum=x-sum;
		dump(sum);
		walk.pb(mp(0,sum));
		sort(ALL(walk));
		ld res=0;
		REP(i,walk.size()){
			if(walk[i].sc>t*(walk[i].fr+r)){
				res+=t;
				walk[i].sc-=(ld)t*(walk[i].fr+r);
				res+=(ld)walk[i].sc/(walk[i].fr+s);
				t=0;
			}else{
				res+=(ld)walk[i].sc/(walk[i].fr+r);
				t-=(ld)walk[i].sc/(walk[i].fr+r);
			}
		}
		printf("Case #%d: %.7f\n",setn+1,(double)res);
		fprintf(fp,"Case #%d: %.7f\n",setn+1,(double)res);
	}
	return 0;
}

Problem B

int main(){
	int t;scanf("%d",&t);
	FILE* fp=fopen("out.txt","w");
	REP(setn,t){
		int r,c,d;scanf("%d%d%d",&r,&c,&d);
		vvi buf(r,vi(c));
		REP(i,r){
			REP(j,c){
				char cc;
				scanf("\n%c",&cc);
				buf[i][j]=cc-'0'+d;
			}
		}
		int sz=min(r,c);
		int res=-1;
		vector<vector<pair<lint,pair<lint,lint> > > > part(r+1,
		vector<pair<lint,pair<lint,lint> > >(c+1));
//2次元の累積和
		REP(i,r){
			REP(j,c){
				part[i+1][j+1].fr=buf[i][j]+part[i][j+1].fr+part[i+1][j].fr
				-part[i][j].fr;
				part[i+1][j+1].sc=mp(i*buf[i][j]+part[i][j+1].sc.fr+part[i+1][j].sc.fr
				-part[i][j].sc.fr,j*buf[i][j]+part[i][j+1].sc.sc+part[i+1][j].sc.sc-
				part[i][j].sc.sc);
			}
		}
		for(sz=min(r,c);sz>=3;--sz){
			REP(i,r-sz+1){
				REP(j,c-sz+1){
					lint sumx=0,sumy=0;
					lint div=0;
					sumx=part[i+sz][j+sz].sc.sc-part[i][j+sz].sc.sc-
					part[i+sz][j].sc.sc+part[i][j].sc.sc;
					sumy=part[i+sz][j+sz].sc.fr-part[i][j+sz].sc.fr-
					part[i+sz][j].sc.fr+part[i][j].sc.fr;
					div=part[i+sz][j+sz].fr-part[i][j+sz].fr-part[i+sz][j].fr+
					part[i][j].fr;
					sumx-=(buf[i][j]*j+buf[i][j+sz-1]*(j+sz-1)
					+buf[i+sz-1][j]*j+buf[i+sz-1][j+sz-1]*(j+sz-1));
					div-=(buf[i][j]+buf[i][j+sz-1]+buf[i+sz-1][j]+buf[i+sz-1][j+sz-1]);
					sumy-=(buf[i][j]*i+buf[i][j+sz-1]*i+buf[i+sz-1][j]*(i+sz-1)+
					buf[i+sz-1][j+sz-1]*(i+sz-1));
					lint x=sumx*2/div,y=sumy*2/div;
					if(y==(sz-1)+i*2 &&  (sumy*2)%div==0 && 
						x==(sz-1)+j*2 && (sumx*2)%div==0){
//ここの条件を、double とEPSつかったりしていろいろしてた
//おそらく精度不足。ちなみにlong double 使っても落ちた
//小数こわい
							res=sz;
							goto exi;
					}
				}
			}
		}
		exi:;
		if(res==-1)
			fprintf(fp,"Case #%d: IMPOSSIBLE\n",setn+1);
		else fprintf(fp,"Case #%d: %d\n",setn+1,sz);
	}


					
	return 0;
}