6133:Cellphone Typing

問題文
https://icpcarchive.ecs.baylor.edu/external/61/6133.pdf

補完機能を使って文字を打つとき、ひとつの文字を打つのに必要な最小の打たなければいけない文字数の平均を求めよ。

トライ木を使った。そのノードの子が2つ以上なら、そこまでで補完機能一回分。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<iomanip>

using namespace std;

struct Trie{
  int value;
  Trie * next[0x100];
  Trie(){
    value=0;
    fill(next,next+0x100,(Trie*)0);
  }
};

void find(string s,Trie *r){
  for(int i=0;i<s.size();i++){
    char c=s[i];
    if(!r->next[c])r->value++,r->next[c]=new Trie;
    r=r->next[c];
  }
}

int getCount(string s,Trie *r){
  int cnt=1;
  for(int i=0;i<s.size()-1;i++){
    char c=s[i];
    if(i>0 && r->value>1)cnt++;
    r=r->next[c];
  }
  return cnt;
}

void Clear(Trie *r){
  for(int i=0;i<128;i++){
    if(r->next[i])Clear(r->next[i]);
    delete r->next[i];
  }
}

int main(void){

  int n;
  while(cin >> n){
    Trie root;
    string s[n];
    for(int i=0;i<n;i++){
      cin >> s[i];
      s[i]+="$";
      find(s[i],&root);
    }
    double ans=0;
    for(int i=0;i<n;i++)ans+=getCount(s[i],&root);
    cout << setiosflags(ios::fixed) << setprecision(2) << ans/(double)n << endl;
    Clear(&root);
  }
  return 0;
}