HackerRank RookieRank2 : E. Prefix Neighbors

なんとなく参加。良い成績だったけど未経験者しかTシャツはもらえないようだ。
https://www.hackerrank.com/contests/rookierank-2/challenges/prefix-neighbors

問題

文字列の集合Sがある。
S中の要素AがBの隣接prefixであるとは、AがBのprefixで、かつAがCのprefixかつCがBのprefixであるようなCが存在しないことをいう。
Sの部分集合のうち、もともとS中で隣接prefixの関係にある2要素を両方とも含むことがない場合を考える。

各文字列のスコアを、各文字のASCIIコードの値の総和とする。
条件を満たすSの部分集合のうち、含まれる文字列のスコアの最大値を求めよ。

解法

各文字列の隣接prefixは1種類だが、1つの文字列が複数の隣接prefixになることはある。
Sに空文字を加えた集合を考えると、隣接prefixの関係は空文字を根とした木を成すグラフとなる。

幸い各文字列は短いので、隣接prefixは末尾を1文字ずつ削ってS中の文字列を探せば容易に見つかる。
あとは上記グラフにおいて、隣接する成分を選択しないようにし、選択成分のスコアの最大値を求めればよい。
これは典型的な木DPで、各SubTreeの根を選択した場合としない場合の最大スコアをそれぞれ求めていく。

int N;
string S[404040];
map<string,int> SS;
int nei[404040];
int mi[404040];
int sc[404040];
vector<int> E[404040];

ll dp[2][404040];

void dfs(int cur,int pre) {
	dp[1][cur]=sc[cur];
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		dp[0][cur] += max(dp[0][e],dp[1][e]);
		dp[1][cur] += dp[0][e];
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	N++;
	FOR(i,N) {
		if(i) cin>>S[i];
		SS[S[i]]=i;
		FORR(c,S[i]) sc[i]+=c;
	}
	
	FOR(i,N) {
		nei[i]=-1;
		if(i==0) continue;
		s=S[i];
		while(s.size()) {
			s.pop_back();
			if(SS.count(s)) {
				nei[i]=SS[s];
				E[nei[i]].push_back(i);
				break;
			}
		}
	}
	
	dfs(0,-1);
	cout<<max(dp[0][0],dp[1][0])<<endl;
	
}

まとめ

むしろ競プロ未経験でこれ通せるのすごくないかい…。