ABC079 D Wall - ymduu+2

D

所感

ワーシャルフロイドを再発明した。ワーシャルフロイドの理解がふわふわしていたのでACした後ブログに書くのに時間がかかった。

Submission #2372327 - AtCoder Beginner Contest 079

問題概要

数字iをjに変えるときに必要なコストがc[i][j]に書かれた表cと数字の表Aが与えられたとき、表Aに書いてある数字を全部1にするための最小コストを求める問題。

取った方針

直接i->jと数字を変えるよりもほかの数kを挟んでi->k->jと変える方がコストが安くなる場合がある。それをすべての数字の対について試し、コストが安くなった場合のみコストの表を更新する。表の更新がなくなるまで更新操作を行えば任意の数字から任意の数字に変更するコストの最小値が求まっているはずである。

 for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < 10; k++) {
                //i,j:使いたい距離 k:参照先の行を走査して、通った方がコストが短くなる数字がある場合更新
                magiMap[i][k] = min(magiMap[i][k], magiMap[i][j] + magiMap[j][k]);
            }
        }
    }

上記の例について、例えばi=0,j=2のとき、0から2に変える場合のコストを使って0から数kに変える場合のことを考える。
k=7なら、0から7に変えるコストと、0から2に変えて7に変えるコストを比較し、小さい方を0から7に変えるコストとして採用する。
i,j,kの順番が一般的なワーシャルフロイドと違うのは、「与えられたコストを用いてほかのコストを更新できるならする」という考え方をしたからである。

正しい方針

上記の方針について、「表の更新がなくなるまで」と表記したが、実際は三重ループ一回で更新できなくなるらしい。(なぜ？)このことをワーシャルフロイド法と言う。

得られた知見

・ある数字iをほかの数字jに変えるコストの表が与えられたとき、それを隣接行列として見ることで、数字をノード、コストを重み付きエッジと見るグラフの問題に帰着することができる。
・(一般化)hogeをpiyoに変えるコストの表が与えられて、その最小コストを求めたいとか言われたらその表をグラフの隣接行列としてみることでグラフアルゴリズムが使える可能性がある。
・ワーシャルフロイド法のつかいかた

解くのに必要な要素

・コストの表を更新できなくなるまで更新すれば任意の数iを任意の数jに変更する最小コストが求まるだろうという考え方 or ・入力がグラフの隣接行列に見える能力+ワーシャルフロイド法

周辺調査によって得られた知見

特になし