E - KarutaをTrie木で解いてみた

• 解説放送でも解の1つとして挙げられていた
• Trie木は使ったことがないので使ってみよう
• アルゴロジックさんのTrie木を参考に拡張した
  • 親側に辿る変数追加など
• 提出AC https://atcoder.jp/contests/abc287/submissions/39835331
• 初めはTLEした
  • Trie::Node変数のサイズがとても大きくなりうるのに値コピーしたため
  • そこをポインターで書き換えると、変更点少なく値コピーを避けることができ、AC
• 解法解説
  • 全文字列をTrieに登録する
  • 各ノードを文字列が何度通ったかはNode.touchにそれぞれ保存されている
  • 葉から辿ってtouch>=2の箇所が、最大に(文字列が)重なった箇所である

code抜粋

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    // input
    ll N;cin>>N;
 
    VS S(N);
    rep(i,N)cin>>S[i];
    
    Trie<26,'a'> trie;
    rep(i,N){
      trie.insert(S[i], i);
    }
 
    rep(i,N){
      string s = S[i];
      ll node_index = trie.get_node_index(s);
      Trie<26,'a'>::Node* now = &trie.nodes[node_index]; // 値渡し・値コピーすると重いのでポインタを使う
      ll cnt=0;
      while(now->touch<2){
        now = &trie.nodes[now->parent_node_index]; // 根側に辿っていく
        cnt++;
      }
      ll ans = s.size() - cnt;
      p(ans);
    }
 
    return 0;
}