1/2 PKU

2949 Word Rings

word ringを、「いくつかの文字列で、i番目の文字列の終わりの2文字がi+1番目の文字列の最初の2文字に一致する（また、最後の文字列の終わりの2文字が最初の文字列の最初の2文字に一致する）ような文字列の列」と定義する。文字列の集まりが与えられた時、それらからいくつか選んでword ringを作り、文字列長の平均を最大化せよ。

二分探索を用いて、平均長をdより大きくできるか考える。
今、k個の文字列（それぞれ長さがL₁, L₂, …, L_k)でword ringを作る時、その平均長がdより大きくなるのは
(L₁-d) + (L₂-d) + … + (L_k-d) > 0
のときである。
各文字列は、最初/最後の2文字とその長さだけ見れば十分である。すると、2文字の組を頂点、「最初の2文字→最後の2文字」は重みがLの辺であるようなグラフであると見なせる。
ここで、word ringはグラフ上の閉路に相当する。先の平均長がdより大きくなる条件を変形すると
(d-L₁) + (d-L₂) + … + (d-L_k) < 0
である。これはグラフ上では、(長さLの文字列に対して重みをd-Lとしたときの）負閉路に相当する。負閉路の発見はBellman-Fordを用いて簡単に行える。
このアルゴリズムはO(精度 * N * 文字種) で動き、Time Limitが長いので普通に実装すると通る。