ABC243 E問題を直感的に考える

AtCoder Beginner Contest 243 のE問題『Edge Deletion』を解いたので、直感寄りの考え方を書いてみます。

問題の解釈

問題を砕いて表現すると、「無くても困らない道はいくつか」となります。

不要な道とは

まずは極端な例で考えてみます。
下の図のように、A, B, C, D の4つの地点と、それらを結ぶ道があるとします。
道に書かれている数字は通行コスト、つまり所要時間や通行料金を表します。

flowchart LR A---|10|B B---|20|C C---|30|D A---|999999|D

ひと目で、 「A-D 直結の道が無くても困らなそうだ」 と感じます。
A-D の行き来には、A-B-C-D という経由ルートが使われることでしょう。

ルート	通行コスト
A-B-C-D 経由ルート	60
A-D 直結ルート	999999

「BからDへ」「AからCへ」など他の組み合わせについても、A-D直結の道を含むルートはとんでもなく高コストになってしまうので、A-D直結の道は不要として良さそうですね。

さて、今回の問題では 経由と直結でコストがぴったり一致する場合も 不要 と扱います。
下のような場合です。

flowchart LR A---|10|B B---|20|C C---|30|D A---|60|D

ルート	通行コスト
A-B-C-D 経由ルート	60
A-D 直結ルート	60

不要な道 の定義

ここまでをまとまめると、
「ある直結の道について、そのコストが 他の経由ルートのコストと同じ あるいは上回る場合、不要」
となります。

では、この言い換えた問題の解き方を考えていきましょう。

最小コスト vs 直結の道

「直結の道を使わない場合の最短ルートは…」と考えると複雑になってしまいます。
そこで、まずはシンプルに 2地点間の最小コスト を求め、そのコストと直結ルートのコストを比べる という方針を考えてみます。

[最小コスト < 直結] のケース

• A～D 間の最小コストを調べたら、60でした。でも、その具体的な経路は覚えていません。どこかを経由するルートだったか、それともA-D直結の道を使ったか…。
• A-D 直結の道があります。そのコストは999999です。

flowchart LR A-.-|最小 60|D A---|999999|D

このとき、「他の地点を経由するルートの中に コスト60 で済むものがあるから、直結の道は不要な道」といえますね。

[最小コスト > 直結] のケース

このケースは、存在しません。
もし導き出した最小コストより低コストなルートがあったとしたら、それが最小コストになっているはずです。

flowchart LR A-.-|最小 100|D A---|60|D

[最小コスト = 直結] のケース

このケースは、どうなるでしょうか。

• 最小コストは60でした。でも、その具体的な経路は覚えていません。
• A-D 直結の道があります。そのコストは60です。

flowchart LR A-.-|最小 60|D A---|60|D

もし、他の地点を経由ルートで同じコストのもの（A - ? - D コスト60）があるなら、直結の道は不要といえます。でも、無いなら必要な道です。

flowchart LR A-.-|最小 20|? ?-.-|最小 40|D A-.-|最小 60|D A---|60|D

では、もし [最小コスト = 直結] のケース に出会ったら、その際には 全ての経由地点を試す ことにしましょう。
具体的には、 A - ? の最小コスト + ? - D の最小コスト を、全ての地点について調べ、それが最小コストと一致するような地点が存在するならば 直結の道は不要 と確定できますね。

最小コスト早見表を作る

さて、ここまで「最小コストを求めておく」という前提部分がありましたが、それはどのように計算すればよいでしょうか。

ワーシャル–フロイド法 Floyd–Warshall Algorithm というアルゴリズムがあります。
これを用いると、全ての2地点ペアの最小コストを O(N^3) で求めることができます。

○○法、というものが登場すると「わけわからん」になりがちですが（少なくとも私はそうです）
実はワーシャル–フロイド法はとてもシンプルで、 3重forでテーブルを更新するだけであらゆる2地点間の最小コストを求められてしまう という使い勝手の良いアルゴリズムなので、是非覚えて使ってみましょう。

ワーシャル–フロイド法

ここではイメージのみを紹介します。正確なアルゴリズムや証明については、調べてみてください。

flowchart LR A---|10|B B---|40|C A---|20|C C---|30|D A---|999999|D

まずは、出発地点と目的地点の表を作ります。
直結の道について、そのコストを書き込みます。

	Aまで	Bまで	Cまで	Dまで
Aから		10	20	999999
Bから	10		40	∞
Cから	20	40		30
Dから	999999	∞	30

値を埋められなかったところは、仮で∞コストということにしました。
この表は、「現時点でわかっている最小コスト」を表します。
ワーシャル–フロイド法では、A, B, C… 地点を順に経由地点として考えてみて、表をアップデートしていきます。

まずは、A地点を経由する場合を考えます。

• 表によると、BからCまで のコストは40とのことです。
• しかし、同じく表から、BからAまでは10 かつ AからCまでは20 で、合計30。つまり、Aを経由したほうが低コスト ということがわかります。
• この表が表すのは、「現時点でわかっている最小コスト」でした。
  なので、先程判明した 30 というコストで上書きします。
  • ついでに、CからBまで も同じ値で上書きします。

	Aまで	Bまで	Cまで	Dまで
Aから		10	20	999999
Bから	10		30	∞
Cから	20	30		30
Dから	999999	∞	30

• また、BからD は不明でしたが、BからAまで + AからDまで の値が判明し、これが「現時点でわかっている最小コスト」となります。

	Aまで	Bまで	Cまで	Dまで
Aから		10	20	10+999999
Bから	10		30	∞
Cから	20	30		30
Dから	999999	10+999999	30

この操作を 全ての地点・全てのセルについて繰り返すと、すべての地点ペアの最小コスト表が完成します。

• A, B, C… 地点を順に経由地点として考えてみて（ O(N) ）
  • 表全体を更新する （O(N^2)）

つまり、計算量は O(N^3) です。

表の更新部分は、3重ループとminのみで実装することができます。
Pythonでの例

for k in range(N):
    for i in range(N):
        for j in range(N):
            table[i][j] = min(table[i][j], table[i][k] + table[k][j])

まとめ

ここまでの方針を繋げると、この問題を解くアルゴリズムが完成します。

1. 入力を受け取り、直結の道の情報を保持する。
2. ワーシャル–フロイド法で「最小コスト表」を作成する。
3. 直結の道それぞれについて、
   • 「最小コスト表」を使って 始点 - ? の最小コスト + ? - 終点 の最小コスト を全ての地点について調べ、最小コストと一致するような地点が存在するなら不要な道と判断
4. 不要な道の総数を出力する。

提出コード

• Python (PyPy3)