AtCoder ABC #358 (CodeQUEEN 2024 予選) : G - AtCoder Tour

普段に比べ問題は難しくないが、しょうもないミスを連発してしまった。
https://atcoder.jp/contests/abc358/tasks/abc358_g

問題

H*Wのグリッドがあり、各マスには非負整数が書かれている。
初期状態で、駒のある位置が指定される。

ここからK回以下を繰り返す。

• 駒を隣接マスに移動するか、今のマスにとどまる。その後、現在位置に書かれた値をスコアに加算する

最終的に得られる最大総スコアを求めよ。

解法

駒を移動させたとき、そのパス上で書かれた整数の最大値のマスにとどまり続けるのが良い。
dp(r,c,k) := kターン後にマス(r,c)にいる場合、そこまでの総取得スコアの最大値

とすると、k＞H*Wになった以降は、基本的にそのマスに居続けると考えてよい。
そこでk≦Kの範囲でdp(r,c,k)を愚直に埋めよう。

int H,W;
int K;
int SY,SX;
int A[55][55];
ll dp[2600][55][55];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	cin>>SY>>SX;
	SY--,SX--;
	FOR(y,H) FOR(x,W) {
		cin>>A[y][x];
		dp[0][y][x]=-1LL<<60;
	}
	dp[0][SY][SX]=0;
	
	FOR(i,2500) {
		FOR(y,H) FOR(x,W) {
			dp[i+1][y][x]=-1LL<<60;
			chmax(dp[i+1][y][x],dp[i][y][x]+A[y][x]);
			if(y) chmax(dp[i+1][y][x],dp[i][y-1][x]+A[y][x]);
			if(x) chmax(dp[i+1][y][x],dp[i][y][x-1]+A[y][x]);
			if(y+1<H) chmax(dp[i+1][y][x],dp[i][y+1][x]+A[y][x]);
			if(x+1<W) chmax(dp[i+1][y][x],dp[i][y][x+1]+A[y][x]);
		}
	}
	
	ll ret=0;
	FOR(y,H) FOR(x,W) {
		if(K<=2500) {
			ret=max(ret,dp[K][y][x]);
		}
		else {
			ret=max(ret,dp[2500][y][x]+1LL*(K-2500)*A[y][x]);
		}
	}
	cout<<ret<<endl;
	
}

まとめ

ABC-Gとしては最近の中ではだいぶ簡単だね。