第一回 アルゴリズム実技検定 J - 地ならし

J - Leveling

概要

H×Wのグリッドが与えられる。各グリッドには非負整数A[i][j]が書かれている。
隣接するグリッドを通って左下マス⇒右下マス⇒右上マスに移動することを考える。このとき、各マスに移動する際は移動先のマスの数字分コストがかかる。ただし、コストがかかるのはそのマスを通る最初の1回のみとする。コスト合計の最小値を求めよ。

制約

2 ≦ H, W ≦ 50
0 ≦ A[i][j] ≦ 100000

方針

左下マスを(H-1, 0)、右下マスを(H-1, W-1)、右上マスを(0, W-1)とする。
マス(a1, b1)からマス(a2, b2)に移動する際にかかる最小コストをdist[(a1, b1), (a2, b2)]とする。
このとき、dist[(a1, b1), (a2, b2)]とdist[(a2, b2), (a1, b1)]は必ずしも等しくない（対称律を満たさない）ことに注意する。

重要な考察として、最小コストを実現する経路はあるマス(s, t)が存在して次が成り立つ。

• 最小コストはdist[((H-1, 0), (s, t)] + dist[(s, t), (H-1, W-1)]+ dist[(s, t), (0, W-1)]
• パス(H-1, 0)→(s, t)、(s, t)→(H-1, W-1) 、(s, t)→(0, W-1)が共通して通るマスは(s, t)のみである。

これより、全てのマス(s, t)に対して上記distを計算し、その最小値を求めればよい。これは(H-1, 0)、(H-1, W-1)、(0, W-1)を起点としてそれぞれダイクストラ法で他の点への最短距離を求めてあげればよさそう…だが前述の通りdistが対称律を満たさないのでそのままではいけない。

仮にdist[(H-1, 0), (s, t)] + dist[(H-1, W-1), (s, t)]+ dist[(0, W-1), (s, t)]としたときに前述のコストとの違いを考えると、
dist[(H-1, W-1), (s, t)]、dist[(0, W-1), (s, t)]を計算する際はすでにマス(s,t)を通っているため、(s, t)に入るコストがかからない。
そのため、dist[(H-1, 0), (s, t)] + dist[(H-1, W-1), (s, t)]+ dist[(0, W-1), (s, t)] - 2*A[s][t]の最小値を探せばよい。

感想

仕組みがわかればダイクストラ3回ですが、グラフの距離の非対称性や「重要な考察」を思いつく部分が難しいと思いました。
こちらは考察の際のメモです。

考察メモ

解答

Submission #10035553 - 第一回 アルゴリズム実技検定 過去問

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
struct edge {ll to, cost;};
typedef pair<ll, ll> P; // firstはsからの最短距離, secondは頂点の番号
const ll INF = LLONG_MAX / 10;
 
const int max_n = 52;
 
vector<edge> g[max_n * max_n];
 
void dijkstra(ll s, vector<ll> &d){
	d[s] = 0;
 
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,s));
 
	while(!que.empty()){
		P p = que.top();
		que.pop();
 
		ll v = p.second;
		if(d[v] < p.first) continue; //後から最短パスが見つかった場合、先にqueに入っているものはここではじかれる
 
		for(ll i = 0; i < g[v].size(); i++){
			edge e = g[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int h, w;
	cin >> h >> w;
 
	int a[h][w];
	rep(i, h) rep(j, w) cin >> a[i][j];
 
	rep(i, h) rep(j, w - 1){
		g[i * w + j].push_back({i * w + j + 1, a[i][j+1]});
		g[i * w + j + 1].push_back({i * w + j, a[i][j]});
	}
 
	rep(j, w) rep(i, h - 1){
		g[i * w + j].push_back({(i+1) * w + j, a[i+1][j]});
		g[(i+1) * w + j].push_back({i* w + j, a[i][j]});
	}
 
	ll sz = h * w;
	vector<ll> d1(sz, INF), d2(sz, INF), d3(sz, INF);
	dijkstra((h-1) * w + 0, d1);
	dijkstra((h-1) * w + w - 1, d2);
	dijkstra(0 * w + w - 1, d3);
 
	ll ans = INF;
	rep(i, h) rep(j, w){
		ans = min(ans, d1[i * w + j] + d2[i * w + j] + d3[i * w + j] - 2 * a[i][j]);
	}
 
	cout << ans << endl;
}