CodeChef January Challenge 2020 - English

• 問題
• AC

まず、接頭辞と接尾辞を両方考慮するという設定は、接頭辞だけの設定に直せる。アルファベットが$26 \times 26$種類あることにして、単語とその反転を合わせて扱えばよい。例えばpoemなら$(p, m)(o, e)(e, o)(m, p)$という列だと思えばよい。

さて、本題は重みつきマッチングだが、一般のマッチングアルゴリズムでは無理なのでgreedyを探す。まず思いつくのはスコアの高いペアからマッチングしていくことで、実はこれでよいことがわかる:

単語$x, y$の最長共通接頭辞の長さを$f(x,y)$とする。また、4つの単語$a, b, c, d$が与えられたとし、$f$が最大になる組み合わせが$\{a, b\}$だとする。このとき、接頭辞の性質により

• $f(c, d) \ge \min(f(c, a), f(a, b), f(b, d))$

が成り立ち、$f(c, d) \ge f(c, a), f(c, d) \ge f(a, b), f(c, d) \ge f(b, d)$のどれを仮定しても$f(a, b)^2 + f(c, d)^2 \ge f(a, c)^2 + f(b, d)^2$が成り立つので$\{a, b\}, \{c, d\}$と組み合わせるのがもっともスコアが高くなる。

したがって、マッチングとそれに含まれる2つのペア$\{u, v\}, \{x, y\}$が与えられた時、4点の中でもっともスコアが高くなる辺を優先してマッチングをつなぎかえても全体のスコアは下がらない。このことより、最大スコアを達成するマッチングは上述のgreedyで得られることが示された。$\square$

実装をどうするかで迷ったが、Trieにすべての単語を登録した上で、DFSして深いものから順にマッチングを決めていった。