![[C#] J – 地ならし [第一回 アルゴリズム実技検定]](https://webbibouroku.com/wp-content/uploads/eye_atcoder.png)
第一回 アルゴリズム実技検定 J – 地ならし を解きたい
C# で参加した第一回 アルゴリズム実技検定(PAST)は、AからI問題まで解けました。J問題は検定中に解けそうで解けなかった問題なので改めて解いてみました。
[C#] AtCoder 第一回 アルゴリズム実技検定 の振り返り │ Web備忘録
AからIまで上の記事で解いてみたコードがあります。
ではJ問題を解いてみます。コードはC#です。
J – 地ならし
縦 H マス、横 W マスの合計 H×W 個の正方形のマスに区切られた区画がある。左下隅、右下隅、右上隅の 3 マスを除いてこれらのマスはすべて未整備で、上から i 行目、左から j 列目 (1≦i≦H,1≦j≦W) のマスを整備するのに必要な費用は Ai,j 円である。
区画の左下隅のマスに物体が置かれている。あなたは、これをまず右下隅のマスまで移動させ、次に右上隅のマスまで移動させようとしている。
物体の移動は、物体が現在占有するマスから上下左右に隣接するマスに動かすことを繰り返して行う。このとき、物体が通るマスはすべて整備されている必要がある。一度整備を行ったマスの上は何度でも物体を通すことができる。
このとき、マスの整備に必要な最小の合計費用を求めよ。
制約
- 2≦H,W≦50
- 0≦Ai,j≦100000
- AH,1=AH,W=A1,W=0
- 入力中の値はすべて整数である。
考えたこと
いわゆる最短経路問題です。ただし2点間の最短経路ではなく寄り道しないといけないのでそこをうまく処理しないといけません。
左下(H-1,0) -> 右下(H-1,W-1) -> 右上(0,W-1)という経路のコストを最小化します。単純にこの間の最短経路を求めてもうまくいきません。なぜなら「一度整備を行ったマスの上は何度でも物体を通すことができる」とあるので、最初に左下から右下へ向かう間に使った経路を再利用する場合はコストがかかりません。
最初に思いついたのは左下から右下への最短経路を求め、その道中から右上までの経路で最も小さいコストを足し合わせたらよいのではということでしたが、これはうまくいきません。
次に思いついたのが、左下->中継地点->右下->中継地点->右上 となるような中継地点を全探索してやれば求まるのではという考えです。
左下->中継地点右下->中継地点右上->中継地点
この3つの最短経路を求めて足し合わせたら中継地点を挟む形で移動するときの最短経路になります。よってこれを最小化する中継地点を全探索して見つけてやればよいです。中継地点が存在しない場合、つまり重複した経路を利用しないパターンも、中継地点が左下や右下に重なる場合で網羅できます。
結論からいうと、この考えであっています。ただしどのように実装するかで間違いました。
最初はワーシャルフロイドで全ペアの最短経路を求めればいいのではと思い実装し、TLEしました。50*50を250だと思って2503=107くらいでOKと思ってたので、はまりました。冷静に計算すると25003なので当然間に合わない計算量でした。
次に全中継地点について、ダイクストラで3点に対して最短経路を求める実装をしてTLEしました。当然です。
正しくは左下、右下、右上の3点について、ダイクストラ法などで単一始点の最短経路を求めればよかったみたいです。解説が普段のABCと違い実装コードがないので詳細は不明ですが、ACしたのでたぶんあってます。
以下、ACしたコードです。
コード
static void Main(string[] args)
{
// 入力
var H = sc.ReadInt();
var W = sc.ReadInt();
var A = new int[H, W];
for (int i = 0; i < H; i++)
{
for (int j = 0; j < W; j++)
{
A[i, j] = sc.ReadInt();
}
}
// 2次元の座標を1次元に変換する関数
Func<int, int, int> toi = (h, w) => h * W + w;
// 最短経路を求めるために各辺のコストを求めておく
var dij = new Dijkstra(H * W);
for (int h = 0; h < H; h++)
{
for (int w = 0; w < W; w++)
{
var ind1 = toi(h, w);
var dh = new int[] { -1, 0, 1, 0 };
var dw = new int[] { 0, -1, 0, 1 };
for (int d = 0; d < 4; d++)
{
var nh = h + dh[d];
var nw = w + dw[d];
if (0 <= nh && nh < H && 0 <= nw && nw < W)
{
var ind2 = toi(nh, nw);
dij.Add(ind1, ind2, A[nh, nw]);
}
}
}
}
// ダイクストラで左下、右下、右上から各頂点へのコストを計算しておく
var p1 = toi(H - 1, 0);
var p2 = toi(H - 1, W - 1);
var p3 = toi(0, W - 1);
var dp1 = dij.Calc(p1);
var dp2 = dij.Calc(p2);
var dp3 = dij.Calc(p3);
// すべての頂点を中継地点とした時のコストの最小値が答え
var ans = long.MaxValue;
for (int h = 0; h < H; h++)
{
for (int w = 0; w < W; w++)
{
var m = toi(h, w);
var cost = dp1[m] + dp2[m] + dp3[m];
// 中継地点のコストが3度計算されているので2回分引く
cost -= A[h, w] * 2;
ans = Math.Min(ans, cost);
}
}
Console.WriteLine(ans);
}
class Dijkstra
{
public int V { get; set; }
public int E { get; set; }
public List<Edge>[] G { get; set; }
public Dijkstra(int n)
{
this.V = n;
this.G = new List<Edge>[V];
for (int i = 0; i < V; i++)
{
this.G[i] = new List<Edge>();
}
}
public void Add(int a, int b, long cost = 1)
{
this.G[a].Add(new Edge(b, cost));
this.E++;
}
public long GetMinCost(int start, int goal)
{
var cost = new long[V];
for (int i = 0; i < V; i++) cost[i] = long.MaxValue;
cost[start] = 0;
var capacity = Math.Max(1, E);
var q = new PriorityQueue<P>(capacity, false);
q.Enqueue(new P(start, 0));
while (q.Count > 0)
{
var p = q.Dequeue();
if (p.Cost != cost[p.A]) continue;
foreach (var e in this.G[p.A])
{
if (cost[e.To] > p.Cost + e.Cost)
{
cost[e.To] = p.Cost + e.Cost;
q.Enqueue(new P(e.To, cost[e.To]));
}
}
}
return cost[goal] == long.MaxValue ? -1 : cost[goal];
}
public long[] Calc(int start)
{
var cost = new long[V];
for (int i = 0; i < V; i++) cost[i] = long.MaxValue;
cost[start] = 0;
var capacity = Math.Max(1, E);
var q = new PriorityQueue<P>(capacity, false);
q.Enqueue(new P(start, 0));
while (q.Count > 0)
{
var p = q.Dequeue();
if (p.Cost != cost[p.A]) continue;
foreach (var e in this.G[p.A])
{
if (cost[e.To] > p.Cost + e.Cost)
{
cost[e.To] = p.Cost + e.Cost;
q.Enqueue(new P(e.To, cost[e.To]));
}
}
}
return cost;
}
public struct Edge
{
public int To;
public long Cost;
public Edge(int to, long cost)
{
this.To = to;
this.Cost = cost;
}
}
public struct P : IComparable<P>
{
public int A;
public long Cost;
public P(int a, long cost)
{
this.A = a;
this.Cost = cost;
}
public int CompareTo(P other)
{
return this.Cost.CompareTo(other.Cost);
}
}
}
class PriorityQueue<T>
{
public readonly T[] Array;
public readonly bool Greater;
public int Count { get; private set; } = 0;
private IComparer<T> Cmp;
public PriorityQueue(int capacity, bool greater = true, IComparer<T> cmp = null)
{
this.Cmp = cmp;
if (cmp == null)
{
this.Cmp = Comparer<T>.Default;
}
this.Array = new T[capacity];
this.Greater = greater;
}
public void Enqueue(T item)
{
this.Array[this.Count] = item;
this.Count += 1;
this.UpHeap();
}
public T Dequeue()
{
this.Swap(0, this.Count - 1);
this.Count -= 1;
this.DownHeap();
return this.Array[this.Count];
}
public T Peek()
{
return this.Array[0];
}
private void UpHeap()
{
var n = this.Count - 1;
while (n != 0)
{
var parent = (n - 1) / 2;
if (this.Compare(this.Array[n], this.Array[parent]) > 0)
{
this.Swap(n, parent);
n = parent;
}
else
{
break;
}
}
}
private void DownHeap()
{
var parent = 0;
while (true)
{
var child = 2 * parent + 1;
if (child > this.Count - 1) break;
if (child < this.Count - 1 && this.Compare(this.Array[child], this.Array[child + 1]) < 0)
{
child += 1;
}
if (this.Compare(this.Array[parent], this.Array[child]) < 0)
{
this.Swap(parent, child);
parent = child;
}
else
{
break;
}
}
}
private int Compare(T a, T b)
{
var c = this.Cmp.Compare(a, b);
if (!this.Greater)
{
c = -c;
}
return c;
}
private void Swap(int a, int b)
{
var tmp = this.Array[a];
this.Array[a] = this.Array[b];
this.Array[b] = tmp;
}
}Func<int, int, int> toi は h,w の2次元座標を1次元に変換する関数です。ダイクストラで扱うために1次元に変換します。
[C#] ダイクストラ法で最短経路を見つけるための実装方法 │ Web備忘録
[C#][VB] 優先度付きキューを実装する方法 │ Web備忘録
Dijkstra クラスと PriorityQueue<T> クラスの実装は上の記事にまとめてます。
その他実装はコメントにある通りです。最短経路を求めるライブラリを用意しておくと、実装自体は難しくありません。
また、以下のコードはある点から上下左右4点の座標を列挙しています。
var dh = new int[] { -1, 0, 1, 0 };
var dw = new int[] { 0, -1, 0, 1 };
for (int d = 0; d < 4; d++)
{
var nh = h + dh[d];
var nw = w + dw[d];
if (0 <= nh && nh < H && 0 <= nw && nw < W)
{
// はみ出さないとなりあった座標 (nh, nw)
}
}このコードは何かの解説放送で使われてたコードなのですがとても便利です。(h, w) に隣接する上下左右4点の座標(nh, nw)をループで列挙します。if文ではみ出さないようにしています。
このコードもよく使うのでスニペットに入れてすぐに呼び出せるようにしておくと便利です。
var dp1 = dij.Calc(p1);
var dp2 = dij.Calc(p2);
var dp3 = dij.Calc(p3);この部分のコードはダイクストラで求めた単一始点の最短経路を格納したテーブルを保持しています。詳しくは実装を確認してください。
以上。
