2019年4月13日に行われた Google Code Jam 2019 Rounnd 1A の1問題である Aliean Rhyme の Python での実装例です。コンペティション中には解くことができなかったのですが、解説を読んで実装できたので忘備録として書いておきます。
問題
いくつかの文字列が与えられ、その末尾 (accent-suffixe) が一致する ペア を作ることができる文字列の数を答える問題です。ここで注意が必要なのは、ペアを作る際に使用できる accent-suffixe は一回のみ使用可能という点です。そのため、Case 4 (PI, HI, WI, FI) では全ての末尾が I で一致していますが、I でペアを作れるのは 1組だけなので、このケースでペアを作れる文字列は 2 つのみとなります。
実装方針
Trie木 を利用します。今回は単語の末尾が一致しているかを判定したいため、入力された文字列を反転してから Trie木を作成します。Trie木では、ルートから末端に行く過程の各ノードに1つの文字列が格納されており、末端までの経路をたどることで元の文字列が復元されます。そのため、2つの文字列の accent-suffixe が一致している場合（今回は文字列を反転しているため）、ルートから途中までは同じ経路をたどり、途中で分岐します。逆に言うと、末端からルートへと向かう際に、2つの経路が合流した場合はその2つの文字列の以降の文字が一致していることを意味します。
以上を踏まえて、以下の方針で問題を解いていきます。
- ペアを作れない文字列の数 (
m) を数え、全文字列の数 (N)から引くことで答えを求める (N - m) - まず、全ての文字列がペアを作れないと仮定
- Trie木の各ノードで、ペアを作っていない文字列が2つ以上いた場合、ペアを作ることができる
- 末端から再帰的に各ノードの
mを求め、2以上の場合はm = m - 2とする - 最終的にルートまで残った
mがペアを作れない文字列の数となる
以下の図の様な Trie木の場合、最終的に 1つの文字列がペアを作ることができません。
Python での実装
以上の方針を Python 3 で実装した一例が以下になります。この実装の注意点として、1文字目が異なる場合どうやってもペアを作ることができないため、1文字目の文字ごとに for-loop で別々に計算する必要があります（46行目）。
Trie木の実装は Getting Started With Tries in Python | TutorialEdge.net を参考にさせてもらいました。
