TopCoder SRM 525(11/29 21:00~23:00)

DropCoins

やるだけ．

public int getMinimum(String[] ss, int K){
	int n=ss.length;
	int m=ss[0].length();
	int[][] sum=new int[n+1][m+1];
	for(int j=0; j<n; j++){
		debug(ss[j]);
		for(int i=0; i<m; i++){
			sum[j+1][i+1]=sum[j+1][i]+sum[j][i+1]-sum[j][i];
			if(ss[j].charAt(i)=='o'){
				sum[j+1][i+1]++;
			}
		}
	}

	int ret=INF;
	for(int y1=0; y1<n; y1++){
		for(int x1=0; x1<m; x1++){
			for(int y2=y1+1; y2<=n; y2++){
				for(int x2=x1+1; x2<=m; x2++){
					// [x1, x2)*[y1, y2)
					int all=sum[y2][x2]+sum[y1][x1]-sum[y1][x2]-sum[y2][x1];
					if(all==K){
						int dx=min(x1*2+(m-x2), x1+(m-x2)*2);
						int dy=min(y1*2+(n-y2), y1+(n-y2)*2);
						ret=min(ret, dx+dy);
						debug(x1, y1, x2, y2, dx+dy);
					}
				}
			}
		}
	}
	return ret==INF?-1:ret;
}

Challenge Phase

TLEになると思ったケースの撃墜に失敗した．

Result

ox- +0/-1 208.09pts. 350th
1704 -> 1699