Codeforces #245 Div1 B. Working out

これもすんなり解けてよかった。
http://codeforces.com/contest/429/problem/B

問題

N*Mの２次元のグリッドがあり、各頂点にスコアがある。
ここで２人の人がグリッド上を移動する。
１人目は左上マスから右または下に１マスずつ移動し、右下マスに移動する。
２人目は左下マスから右または上に１マスずつ移動し、右上マスに移動する。

２人がともに通るマスを１個だけにした上で、両者が通過するマスの総スコアを最大化せよ。
なお、２人がともに通るマスは同じタイミングであってもなくても良い。
また、２人が通るマスのスコアは総スコアに含まない。

解法

２人がともに通るマス(以下共通マス)を１つにするには、２人が以下のいずれかで進まなければならない。

• １人目は共通マスの左から共通マスに入り右に抜ける。２人目は下から入って上に抜ける。
• １人目は共通マスの上から共通マスに入り下に抜ける。２人目は左から入って右に抜ける。

よって、共通マスを総当たりしておき、それぞれ以下の最大値を求めればよい。

• (１人目が左上→共通マスの左マスへ移動する最大スコア)+(１人目が共通マスの右マス→右下へ移動する最大スコア)+(２人目が左下→共通マスの下マスへ移動する最大スコア)+(２人目が共通マスの下マス→右上へ移動する最大スコア)
• (１人目が左上→共通マスの上マスへ移動する最大スコア)+(１人目が共通マスの下マス→右下へ移動する最大スコア)+(２人目が左下→共通マスの左マスへ移動する最大スコア)+(２人目が共通マスの→マス→右上へ移動する最大スコア)

事前に１人目用に左上から各マス及び各マスから右下、２人目用に左下から各マス、各マスから右上への最大スコアをDPでO(NM)で求めておくと、各マスにつき上記最大値はO(1)で求まる。
後は共通マスがO(NM)あるので、全体の計算量はO(NM)。

int N,M;
int A[1001][1001];
ll dp[4][1001][1001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(y,N) FOR(x,M) cin>>A[y][x];
	
	FOR(y,N) FOR(x,M) { // dr
		dp[0][y][x]=max((y>0)?dp[0][y-1][x]:0,(x>0)?dp[0][y][x-1]:0)+A[y][x];
	}
	for(y=N-1;y>=0;y--) for(x=M-1;x>=0;x--) { //ul
		dp[1][y][x]=max((y<N-1)?dp[1][y+1][x]:0,(x<M-1)?dp[1][y][x+1]:0)+A[y][x];
	}
	for(y=N-1;y>=0;y--) FOR(x,M) { //ur
		dp[2][y][x]=max((y<N-1)?dp[2][y+1][x]:0,(x>0)?dp[2][y][x-1]:0)+A[y][x];
	}
	FOR(y,N) for(x=M-1;x>=0;x--) { //dl
		dp[3][y][x]=max((y>0)?dp[3][y-1][x]:0,(x<M-1)?dp[3][y][x+1]:0)+A[y][x];
	}
	
	ll ma=0;
	for(y=1;y<N-1;y++) for(x=1;x<M-1;x++) {
		ma=max(ma,dp[0][y][x-1]+dp[1][y][x+1]+dp[2][y+1][x]+dp[3][y-1][x]);
		ma=max(ma,dp[0][y-1][x]+dp[1][y+1][x]+dp[2][y][x-1]+dp[3][y][x+1]);
	}
	cout << ma << endl;
	
}

まとめ

２人の共通マスの抜け方を考えるのが面白い問題だった。