2012 WUPC2 : C - 至高のケーキ

では３問目。
難易度自体は低いけどちょっと面倒な実装ゲー。
http://wupc2nd.contest.atcoder.jp/tasks/wupc_03

各マス目に得点があり、階段状にマス目を囲って合計得点の最大値を求める。
安直に組むとO(N^4)程度かかるが、N<=30なので特に問題ない。
階段状の取り方は４通りあるので、それぞれ地道に計算していく。

for文やif文の範囲の取り方に気を付けて書いていけばよい。

int H,W;
char str[50][50];
int mv=0;

int calc1(int sx,int sy,int len) {
	int tmv=-1,t=0;
	int x,y,dy,dx;
	
	//右上
	for(dy=0;dy<=len;dy++) {
		y = sy+dy;
		for(dx=0;dx<=len-dy;dx++) {
			x = sx + dy + dx;
			if(str[y][x]=='X') {
				t=-1;
				goto out1;
			}
			t += str[y][x]-'0';
		}
	}
	tmv = max(tmv,t);
	out1:
	
	t=0;
	//左下
	for(dy=0;dy<=len;dy++) {
		y = sy+dy;
		for(dx=0;dx<=dy;dx++) {
			x = sx + dx;
			if(str[y][x]=='X') {
				t=-1;
				goto out2;
			}
			t += str[y][x]-'0';
		}
	}
	tmv = max(tmv,t);
	out2:
	return tmv;
}


int calc2(int sx,int sy,int len) {
	int tmv=-1,t=0;
	int x,y,dy,dx;
	
	//左上
	for(dy=0;dy<=len;dy++) {
		y = sy-dy;
		for(dx=0;dx<=dy;dx++) {
			x = sx + dx;
			if(str[y][x]=='X') {
				t=-1;
				goto out1;
			}
			t += str[y][x]-'0';
		}
	}
	tmv = max(tmv,t);
	out1:
	
	t=0;
	//右下
	for(dy=0;dy<=len;dy++) {
		y = sy-dy;
		for(dx=0;dx<=len-dy;dx++) {
			x = sx + dy+dx;
			if(str[y][x]=='X') {
				t=-1;
				goto out2;
			}
			t += str[y][x]-'0';
		}
	}
	tmv = max(tmv,t);
	out2:
	return tmv;
}

void solve() {
	s64 res;
	s64 i,j;
	int x,y,l;
	
	H=GETi();
	W=GETi();
	ZERO(str);
	FOR(y,H) GETs(str[y]);
	
	mv=0;
	FOR(y,H) FOR(x,W) {
		//右下
		FOR(l,30) {
			if(y+l>=H || x+l>=W) break;
			mv = max(mv, calc1(x,y,l));
		}
		//右上
		FOR(l,30) {
			if(y-l<0 || x+l>=W) break;
			mv = max(mv, calc2(x,y,l));
		}
	}
	
	_P("%d\n",mv);
}

まとめ

こういう問題、もうちょいスマートに書きたいな。
自分は４通りベタ書きしちゃったけど、AtCoderの他の回答を見ると、うまく４通りをループで回して似たコードを書くことを避けてる人もいるね。