ABC 079 D - Wall のメモ
解いてみました。
考察
ある数値を直接1へ変えることは可能ですが、それが最適とは限らない（他の数値を経由すると消費魔力が少なくて済む可能性がある）ので全部調べる必要がありそうです。
ここで、これは数値が頂点で遷移が辺の有向グラフとして表すことができそうです。消費魔力がコストの重み付きグラフです。
（と言いつつ、その発想に至るまでにやたらと時間がかかったのですが…）
なので、ある頂点から1に行くためのルートを全部調べて、最も消費魔力の合計が小さい場合の数値を頂点ごとに求めて、それを出力すればいいだろうと。0 -> 1のケース、0 -> 2 -> 1のケース、0 -> 2 -> 3 -> 1のケース... などを全部調べます。
これはDFSなどでグラフを全部走査すれば実現できます。
隣接リストでDFSする実装
まずは、こんな感じのコードで解くことができました。
import kotlin.math.min
fun main() {
Thread(
null,
{
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
val c = Array(10) {
readLine()!!.split(" ").map { it.toInt() }.toIntArray()
}
val a = Array(h) {
readLine()!!.split(" ").map { it.toInt() }.toIntArray()
}
val graph = Array(10) { mutableListOf<Pair<Int, Int>>() }
for(i in 0 until 10) {
for(j in 0 until 10) {
if(i == j) {
continue
}
graph[i].add(j to c[i][j])
}
}
val seen = mutableSetOf<Int>()
val memo = IntArray(10) { Int.MAX_VALUE }
for(i in 0 until 10) {
if(i == 1) {
continue
}
dfs(i, i, graph, seen, memo, 0)
}
var ans = 0L
for(i in 0 until h) {
for(j in 0 until w) {
if(a[i][j] == -1 || a[i][j] == 1) {
continue
}
ans += memo[a[i][j]]
}
}
println(ans)
},
"",
128 * 1024 * 1024
).start()
}
fun dfs(start: Int, x: Int, graph: Array<MutableList<Pair<Int, Int>>>, seen: MutableSet<Int>, memo: IntArray, sum: Int) {
seen.add(x)
for(node in graph[x]) {
val currentSum = sum + node.second
if(node.first == 1) {
memo[start] = min(memo[start], currentSum)
continue
}
if(node.first in seen) {
continue
}
seen.add(node.first)
dfs(start, node.first, graph, seen, memo, currentSum)
seen.remove(node.first)
}
seen.remove(x)
}
重み付きグラフを扱ったのが実は初めてだったかもしれません。重みについては、辺を扱う型をPairにすれば表現できます。Pairのfirstが辿る先の頂点の番号、secondが重みです。
実装はけっこう沼りました…
ポイントは訪問済の頂点には行かないようにする点です。訪問済フラグのライフサイクルに注意が必要です。今回のグラフだと、各頂点は全て相互に訪問可能となっているので、訪問済フラグを立てないと無限ループになります。たとえば0 -> 2 -> 3 -> 2のように同じ頂点に訪問することは防ぐ必要があります。
しかし、0 -> 2 -> 1と遷移した後に2を単純に訪問済とすると、0 -> 2 -> 3 -> 1のような探索をせずに打ち切られてしまうといった問題が起こります。
そのために、適宜訪問済フラグの解除を行なっています。（フラグというかSetの要素ですが）
計算量をちゃんと見積もっていなくて、大丈夫かなと心配だったのですが、大丈夫でした。この問題だとグラフの大きさは入力に関わらず一定なので、サンプルで問題なければ全てのテストケースで実行速度としては問題ないということで。
隣接行列でDFSする実装
前述のコードでACできましたが、一応解説も見ました。すると、ワーシャルフロイド法を使うと良いと書いてありました。聞いたことはあるけど知らない子です。
とりあえずググってみました。いくつかのサイトを参照すると、ワーシャルフロイド法を使う場合はグラフを隣接行列で扱うのが一般的のように見えました。
上記の解法だとグラフを隣接リストで扱っています。私はそれしか知らなかったので。
なので、ワーシャルフロイド法の前に隣接行列でグラフを扱うのを試してみようと思いました。
上記のコードを隣接行列でグラフを扱うように書き換えたのが以下です。
import kotlin.math.min
fun main() {
Thread(
null,
{
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
val c = Array(10) {
readLine()!!.split(" ").map { it.toInt() }.toIntArray()
}
val a = Array(h) {
readLine()!!.split(" ").map { it.toInt() }.toIntArray()
}
val seen = mutableSetOf<Int>()
val memo = IntArray(10) { Int.MAX_VALUE }
for(i in 0 until 10) {
if(i == 1) {
continue
}
dfs(i, i, c, seen, memo, 0)
}
var ans = 0L
for(i in 0 until h) {
for(j in 0 until w) {
if(a[i][j] == -1 || a[i][j] == 1) {
continue
}
ans += memo[a[i][j]]
}
}
println(ans)
},
"",
128 * 1024 * 1024
).start()
}
fun dfs(start: Int, i: Int, c: Array<IntArray>, seen: MutableSet<Int>, memo: IntArray, sum: Int) {
seen.add(i)
for(j in c[i].indices) {
val currentSum = sum + c[i][j]
if(j == 1) {
memo[start] = min(memo[start], currentSum)
continue
}
if(j in seen) {
continue
}
seen.add(j)
dfs(start, j, c, seen, memo, currentSum)
seen.remove(j)
}
seen.remove(i)
}
ここで初めて、この問題の
なのでグラフを扱うためのデータ構造を作る処理が丸々消えました。
また隣接行列だと二次元配列の各要素で重みを扱えるため、Pairも消えました。重み付きグラフは隣接行列のほうが扱いやすいみたいですね。
ワーシャルフロイド法を使った実装
ワーシャルフロイド法とはなにかみたいな説明は省きます。（よくわかってないので！）
実装としては以下のようになりました。
import kotlin.math.min
fun main() {
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
val c = Array(10) {
readLine()!!.split(" ").map { it.toInt() }.toIntArray()
}
val a = Array(h) {
readLine()!!.split(" ").map { it.toInt() }.toIntArray()
}
// ワーシャルフロイド
for(k in 0 until 10) {
for(i in 0 until 10) {
for(j in 0 until 10) {
c[i][j] = min(c[i][j], c[i][k] + c[k][j])
}
}
}
var ans = 0L
for(i in 0 until h) {
for(j in 0 until w) {
if(a[i][j] == -1 || a[i][j] == 1) {
continue
}
ans += c[a[i][j]][1]
}
}
println(ans)
}
三重ループでなんかやってみるだけです。シンプルですが、これでバッチリ通りました。不思議…
意味としては、
3頂点しか見ていないので、4頂点以上のケースについてもこれで網羅できるのがなんか不思議な感じがします。
まあ c[i][k] と c[k][j] については、直接遷移時の値とは限らず、コストが最小となるルートの場合の値で上書きされているのでOKってことなんでしょうね。
理解したとはいえないですが、ワーシャルフロイド法を使うとすごく簡単に実装できるので覚えておこうと思います。
（執筆時間: 37分36秒）
Discussion