ABC 338 Dの解法

公式の解説や参加者の解説記事を読んでも、何でこれで上手くいくのか理解できなかったので、自分なりに理解できた解法を書いてみる。

解法のアプローチは以下をベースにして考えた。（もしかしたら同じなのかもしれない）

例として5つの島（橋）、5箇所を巡るツアーを考えてみる。

島と橋の番号

5 5
2 5 3 4 1

橋5が使えない場合の最短ルート

tkzwhr 3ヶ月前に更新

とりあえず、このツアーについて、橋を閉鎖する全パターンの移動距離を橋0から5まで順番に洗い出してみる。
（数が少ないので机上でできる）

移動順^[1]	移動ルート	橋0(=橋5)を閉鎖する	橋1を閉鎖する	橋2...	橋3...	橋4...	橋5...
0	2→5	3(2>3>4>5)	3	2(2>1>5)	2	2	3(2>3>4>5)
1	5→3	2(5>4>3)	2	2	3(5>1>2>3)	3	2(5>4>3)
2	3→4	1(3>4)	1	1	4(3>2>1>5>4)	1(3>4)	1
3	4→1	3(4>3>2>1)	2(4>5>1)	2	2	3(4>3>2>1)	3
合計	-	9	8	7	11	9	9

橋2を閉鎖したときが最短距離で7となる。

ここからわかることは次の通り。

移動距離は必ず2パターン
- 橋は島をリング状に繋いでおり、その移動ルートは左回りか右回りの2パターンしかないため。
移動距離の2パターンは足すと $N$ になる
- 橋は島をリング状に繋いでいるため、1周するには橋をすべて1度ずつ使う必要がある。島 $i$ から島 $j$ を経由して1周することを考えると、島 $i$ から島 $j$ まで右回りで進んだときの距離が $l$ なら、また右回りで島 $i$ まで戻ってくる距離は $N - l$ である。そして、これは島 $i$ から島 $j$ まで左回りで進んだときの区間と一致する。
橋 $0$ を除けば、右回りか左回りかの変化は各移動順ごとで必ず2回だけ起こる
- 島 $i\toj (i<j)$ を右回りに移動するとき、必ず $i, i+1, i+2, ... , j-1, j$ と移動することになり、橋の閉鎖の仕方も $0, 1, ... , N$ と順番にしているため、橋の閉鎖が $i$ に差し掛かると右回りが使えなくなり、橋の閉鎖が $j+1$ まで到達するとまた右回りができるようになる。
回り方の変化が起こる場所は移動ルートの島番号と一致する
- 変化する場所が島番号と一致するのは、島番号 $i\toi+1$ を橋番号 $i$ としたため。 $i\toi+1$ を橋番号 $i+1$ とする考え方でも解けるが、前者のほうがより直感的だと思ったのでこうした。

脚注

今後のコードの都合で0始まりにしている ↩︎

tkzwhr 3ヶ月前に更新

わかったことからアプローチを考えてみる。

$X_1→X_2, X_2→X_3, ... , X_{M-1}→X_M$ の各移動順について、橋が閉鎖されたことで回り方の向きが変わる場所を洗い出す
- 移動順の数は $M-1$ なので $O(M)$
橋 $0$ (=橋 $N$ )を閉鎖した場合の各移動順の移動距離を計算する
- これも $M-1$ なので $O(M)$
橋 $i(i=1,2,...,N-1)$ を閉鎖した場合、橋 $i-1$ から回り方の向きが変わることでの距離変化を計算する
- 以下の処理を $N-1$ 回行う必要があるので $O(Nn)$ （ $n$ は各橋での計算量）
  - 変換点の取得は各橋で必要。手順1で効率の良いデータ構造を使えば $O(1)$
  - 変換点での距離変化の計算をして、橋 $i-1$ で計算した距離から差分更新をする。この計算は各橋で必ずしも必要になるわけではなく、全体として $2M$ ^[1] なので、各橋で見た場合は $O(\frac{M}{N})$
  - よって $n = 1+\frac{M}{N}$
- よって $O(N(1+\frac{M}{N})) = O(N+M)$
2と3で計算した各移動距離のうち最短のものを出力する
- $O(N)$

ということで、 $O(N+M)$ で解ける。

脚注

ここについては例として100の島と、10万の島に対して訪問する島が3箇所だけという状況で考えてみるとわかりやすい。回り方が変わることによる再計算は6回であるため、橋の閉鎖によって回り方が変わる橋が完全に相違だったとしても、前者では94、後者では99,994の橋では閉鎖による回り方の変化は起きないことになる。つまり、この計算が必要な頻度は、 $M$ が同じであれば、 $N$ が大きいほど少なくなるはずである。 ↩︎

tkzwhr 3ヶ月前に更新

ステップ1: $X_1→X_2, X_2→X_3, ... , X_{M-1}→X_M$ の各移動順について、橋が閉鎖されたことで回り方の向きが変わる場所を洗い出す

移動順	移動ルート
0	2→5
1	5→3
2	3→4
3	4→1

移動順になっているデータを、各橋ごとに変換点となっている移動順の対応として持てばよい。これは連想配列を使えばできる。

橋番号	この橋が変換点となっている移動順
1	3
2	0
3	1, 2
4	2, 3
5^[1]	0, 1

脚注

橋Nは橋0として最初に計算してしまう関係で、実際にはこのデータは使わない ↩︎

tkzwhr 3ヶ月前に更新

ステップ2: 橋 $0$ (=橋 $N$ )を閉鎖した場合の各移動順の移動距離を計算する

これ単に下記の繋がり方をした島の移動距離を考えればいいだけである。

島1 ー 島2 ー 島3 ー 島4 ー 島5

単純な等差数列になっているので、例えば移動順0（島2→島5）の移動であれば $|2-5|=3$ で、移動順1（島5→島3）の移動であれば $|5-3|=2$ である。

一般化すれば

distance(移動順i) = |X_i - X_{i+1}|

である。

tkzwhr 3ヶ月前に更新

ステップ3: 橋 $i(i=1,2,...,N-1)$ を閉鎖した場合、橋 $i-1$ から回り方の向きが変わることでの距離変化を計算する

前述した通り、橋 $i$ が回り方の変換点であるならば、その距離は橋 $i-1$ の距離を $l$ とすると $N-l$ に変化する。

橋3を例に考えてみる。橋2での閉鎖では

移動順	移動ルート	橋2...
0	2→5	2(2>1>5)
1	5→3	2
2	3→4	1
3	4→1	2

（一部抜粋して再掲）

となっており、その移動距離は $2+2+1+2=7$ であった。

橋3の閉鎖では、移動順1と移動順2で回り方が変わることになるため、それぞれ計算してみる。

移動順1: 橋2の閉鎖では2だったので $5-2=3$ 、つまり橋2の距離から見ると $+1$ になった
移動順2: 橋2の閉鎖では1だったので $5-1=4$ 、つまり橋2の距離から見ると $+3$ になった

この2つの変化はトータルで考えると $+4$ の距離変化であると分かり、その総距離は $7\to11$ と変化したことがわかる。

同じことを橋 $1$ から橋 $N-1$ まで順次調べていけば、すべての橋を閉鎖したパターンについて総距離を求めることができ、最初に行っていた机上計算と同じ表を作れたことになる🎉

コードはこちら。

このスクラップは3ヶ月前にクローズされました

ステップ1: X_1→X_2, X_2→X_3, ... , X_{M-1}→X_M の各移動順について、橋が閉鎖されたことで回り方の向きが変わる場所を洗い出す

ステップ2: 橋0(=橋N)を閉鎖した場合の各移動順の移動距離を計算する

ステップ3: 橋i(i=1,2,...,N-1)を閉鎖した場合、橋i-1から回り方の向きが変わることでの距離変化を計算する

ステップ1: $X_1→X_2, X_2→X_3, ... , X_{M-1}→X_M$ の各移動順について、橋が閉鎖されたことで回り方の向きが変わる場所を洗い出す

ステップ2: 橋 $0$ (=橋 $N$ )を閉鎖した場合の各移動順の移動距離を計算する

ステップ3: 橋 $i(i=1,2,...,N-1)$ を閉鎖した場合、橋 $i-1$ から回り方の向きが変わることでの距離変化を計算する