【AtCoder】【C#】AtCoder Beginner Contest 079 D-Wall
ABC079のD問題、Wallを解きました。自分の解答でACできたのですが、想定解答をみたらワーシャルフロイドを使用していたので(自分の解答では使用していない)、次回同じような状況になった時にちゃんとワーシャルフロイドを使用できるようにポイントをまとめます。
最初は自分の解法の説明で、最後にポイントをまとめています。
はじめに
本題にむけて必要な情報をまとめます。
問題へのリンク
ワーシャルフロイドとは
重み付き有向グラフの全ペアの最短経路問題を解くためのアルゴリズムです。
以前、ワーシャルフロイドを実装したときの記事が下記になります。
計算量はなにか
O(V3) (V : 頂点の数)なので、AtCoderではノードの数が102ぐらいまでなら計算量として間に合うかと思います。
本題
まず、自分の解法と思考法を整理して、そのあとワーシャルフロイドを使うポイントについて考えます。
自分の解法
まず、今回の問題において、 1 に変えたい値は 0-9 であることがわかっています。そして、A_ijが-1の時はコストを無視して良いということもわかっています。
大方針として、まずは0-9の各値を1にするコストを計算して、各値の出現個数と掛けて足し合わせます。そのため、どうやって0-9を1にするコストを計算するのかがポイントです。
どうやってコストを計算しているのか
わかりにくいかもしれないので、問題の中にある例題を使います。
2 4 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 2 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 2 9 9 9 0 9 9 2 9 9 9 9 9 9 9 0 -1 -1 -1 -1 8 1 1 8
Aに8があるので、8を1にするコストを例に見ていきましょう。
まず、8を1にするコストを調べます。これには9かかります(c_81が9のため)。では、8を他の値にするコストを見てみます。そうすると、8から4にする場合は2ですむことがわかります。
そこで、一度4に遷移させたとして、4の行を見てみます。4から1にする場合を考えます。4から1にするコストは9かかるので、8->4->1の場合は11かかります。これは8->1よりも高いので、候補からはずします。
ただ、4の場合4->9になるケースはコストが2ですみます。9になっても8->4->9のコストは4ですんでいます。なので、次は9を見ていきましょう。
9->1になるコストは2ですみます。つまり、8->4->9->1は6ですむことがわかりました。ここまできたら、 Min(8->1のコスト, 8->4->9->1のコスト)で低い方が採用されます。
これを、再帰処理で計算して、0-9の1になる最小コストを求めます。
これであとは各値の出現個数にこのコストを掛けてすべて足せば答えとなります。
実装について
static void Change(int start, int now, int cost) { //if (start == 8) Console.WriteLine(cost); for (int next = 0; next < 10; next++) { if (next == now) continue; cost += c[next, now]; if (next == 1) { res[start] = Math.Min(res[start], cost); } if (cost < res[start]) Change(start, next, cost); cost -= c[next, now]; } }
実装のリンク
想定解法
想定解法通り、ワーシャルフロイドでの実装をしてみました。下記が実装のポイントです。
for (int y = 0; y < C; y++) { input = Console.ReadLine().Split().Select(int.Parse).ToArray(); for (int x = 0; x < C; x++) { dist[x, y] = input[x]; } } for (int k = 0; k < C; k++) { for (int i = 0; i < C; i++) { for (int j = 0; j < C; j++) { dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]); } } }
各遷移コストの表をまずは二次元配列dist変数に格納します。その後にワーシャルフロイドで最短経路を求めます。
実装のリンク
どう考えるか
これは、0-9までの値をもつノードから1の値を持つノードへ最短経路で移動する問題だと捉えることができます。
多分、なれている人からすると常識なのかもしれないですが、私が今回の問題を解いた中で
- 始点と終点がある(最初の状態と最後の状態も定義がある)
- 状態が遷移していく可能性がある(今回は値がうつっていく)
- 遷移したときのコストが二次元配列で管理されている
こういった条件があれば、グラフ問題へと置き換えていいのではないかなと考えました。そのため、今回のように問題分からグラフであることが明示されていないとしても、上記に当てはまるればグラフ問題だと捉えて考察すると良いのかなと。
感想
再帰処理でもあっていたが、実装に時間がかかりすぎているので本番だったら解答できていなかったなと思いました。もっと集中してはやく解けるようにしないと緑を解くのは難しいのかなと感じました。
