やりたいことは、同時に選べない $i,j$ 間に辺を張ったグラフにおける
重み付き最大独立集合だが、一般的な解法はNP困難（NP完全?）とされている。
今回は、辺を有向（含む方→含まれる方）にした場合、「DAGである」
「$i→j,j→k$ に辺があれば、$i→k$ にも必ず辺がある（推移律）」という性質がある。
この場合は、Dilworthの定理を使えば解ける。
※ $S_i$ に全く同じ文字列が含まれる場合はDAGとは限らなくなるが、
$S_i$ が同じ同士では $A_i$ が最大のものを残して削除するなどの前処理をすればよい。
Dilworthの定理によると、
推移律を満たすDAG
1)では、「最小パス被覆＝最大独立集合」である
最大独立集合はNP完全だが、最小パス被覆は二部グラフの最大マッチング問題に変換できて解ける。
グラフをパスに分割するとは、「各頂点の入次数・出次数が1を超えないように、辺を選ぶ」といえる
辺を $k$ 個選んだ場合、どのような選び方であろうとパスの本数は $N-k$ 本である
よって、「パスの個数の最小化＝選ぶ辺の個数の最大化」と言い換えられる
出る側の頂点を左、入る側の頂点を右に置いた二部マッチングで解ける
今回の場合は単なる最大独立集合ではなく、$A_i$ による重み付きだが、
これは二部マッチングを最大流で解くときの辺の容量を調整すればよい。
始点 $S$、終点 $T$、出る側頂点 $1,...,N$、入る側頂点 $1',...,N'$ の $2N+2$ 個の頂点を用意
$S→i$ に容量 $A_i$ の辺
$i'→T$ に容量 $A_{i'}$ の辺
$S_i$ が $S_j$ を含んでいれば $i→j'$ に容量 $\infty$ の辺
これで、$\sum A_i - \rm{MaxFlow}(S→T)$ が答えとなる。
Python3
from atcoder import maxflow
def remove_same_string(n, sss, aaa):
# 縮約 同じ文字列は最善のもののみ残す
same_string = {}
available_index = set(range(n))
for i, s in enumerate(sss):
if s not in same_string:
same_string[s] = i
continue
j = same_string[s]
if aaa[i] > aaa[j]:
available_index.remove(j)
same_string[s] = i
else:
available_index.remove(i)
available_index = sorted(available_index)
n = len(available_index)
sss = [sss[i] for i in available_index]
aaa = [aaa[i] for i in available_index]
# ついでに s が短い順にソート
order = sorted(enumerate(sss), key=lambda s: len(s[1]))
sss = [s for i, s in order]
aaa = [aaa[i] for i, s in order]
return n, sss, aaa
def solve(n, sss, aaa):
n, sss, aaa = remove_same_string(n, sss, aaa)
mf = maxflow.MFGraph(n * 2 + 2)
s = n * 2
t = s + 1
INF = 1 << 60
for i in range(n):
s1 = sss[i]
for j in range(i + 1, n):
s2 = sss[j]
if s1 in s2:
mf.add_edge(i, j + n, INF)
mf.add_edge(s, i, aaa[i])
mf.add_edge(i + n, t, aaa[i])
ans = sum(aaa)
ans -= mf.flow(s, t)
return ans
n = int(input())
sss = [input() for _ in range(n)]
aaa = list(map(int, input().split()))
ans = solve(n, sss, aaa)
print(ans)
0-1整数計画問題として扱える。
こういった問題はソルバを使える。
AtCoderのPythonで使えるソルバライブラリには、PuLP、OR-Tools、scipy.optimize、z3-solver などがある。
PuLPで解かせてみたところ、ほとんどは高速に解けるが、2ケースでTLEとなった。
（提出一覧には一部通っている提出もあるが、記事執筆時点では、PuLPで通している提出は時間のかかるケースを例外処理していたりする）
一方、OR-Toolsでは、特に例外処理せずとも全てのケースを高速に（200ms以内で）通すことができた。
また、scipyで通している例も見られた。
具体的に中身で何をやってるか不勉強にして分かっていないのだが、ソルバによっても得手不得手があるらしい。
AtCoderのPuLPで使えるソルバはCBC（COIN-OR Brand-and-Cut）のみだが、
今回はこれで時間がかかってしまうテストケースが含まれていたのかもしれない。
（生成AI使って競プロするのがどうのこうのという話がたまに話題になるが、
中身分かってなくても汎用的に使えてしまうという意味ではソルバも大概だな）
2)
Python3
from ortools.sat.python import cp_model
def solve(n, sss, aaa):
model = cp_model.CpModel()
xxx = [model.NewBoolVar(str(i)) for i in range(n)]
for i in range(n):
s1 = sss[i]
for j in range(i + 1, n):
s2 = sss[j]
if s1 in s2 or s2 in s1:
model.AddAtMostOne([xxx[i], xxx[j]])
model.Maximize(sum(x * a for x, a in zip(xxx, aaa)))
solver = cp_model.CpSolver()
solver.Solve(model)
ans = int(solver.ObjectiveValue())
return ans
n = int(input())
sss = [input() for _ in range(n)]
aaa = list(map(int, input().split()))
ans = solve(n, sss, aaa)
print(ans)