【Trie木】ABC377G - Edit to Match の図説

 

この記事でやること

ABC377G-Edit to Match の図説です。やってることは公式解説と同じです。

 

解法

便宜上 S_0 を空文字列として、 S_0, \dots, S_3 まで処理済みで S_4 を \text{push} したTrie木を考えます。（Trie木を知らない方は、参考文献に記載した記事などを参照してください。）

 

S_4 を \text{push} したTrie木

ここで、 S_4 に対する解は \text{min}_{0 \le i \lt 4} \{\text{dist}(S_4, S_i)\} になります。上図の場合、 S_4 から S_0 または S_2 が最短で、答えは 3 になります。

これは、各ノード v について v.dp := v を根とする部分木内での \text{min}_{0 \le i \lt 4} \{\text{dist}(v, S_i)\} を記録しておくことで高速に解くことができます。

\color{blue}{v.dp}、部分木内に S が存在しない場合は ∞

Trie木の根から S_4 のノードまでのパスを P としたとき、求める解は \text{min}_{v \in P} \{v.dp + \text{dist}(v, S_4)\} となります。

また、 v.dp は \text{push} の帰りがけにchminすることで簡単に更新できますね。

帰りがけにchmin

計算量は、各文字列 S_i に対し \mathcal{O}(|S_i|)*1 になります。

 

提出コード

Python (PyPy 3.10-v7.3.12)

Submission #59196277 - TOYOTA SYSTEMS Programming Contest 2024（AtCoder Beginner Contest 377)

 

おわりに

公式解説、こういう挿絵とかあったらもっとわかりやすいのにね…。

 

参考文献

トライ木(Trie木) の解説と実装【接頭辞(prefix) を利用したデータ構造】 | アルゴリズムロジック

*1:Trie木の枝をhashmapで持った場合の期待計算量。配列で持つなら文字種数σ倍が付きます。