■

最長しりとりは、 勉強会でやっている。こんな感じ。

from pulp import *
with open('cpp11_keywords.csv') as fp:
    l = [s.rstrip() for s in fp.readlines()]
    nl = len(l)
    rl = range(nl)
arcs = [] # アークとする
aout = [[] for i in rl] # 出るアーク
ain = [[] for i in rl] # 入るアーク
for i in rl:
    si = l[i][-1:]
    for j in rl:
        if i == j: continue
        sj = l[j][:1]
        if si == sj:
            k = len(arcs)
            aout[i].append(k)
            ain[j].append(k)
            arcs.append((i, j, k))
na = len(arcs)
m = LpProblem('shiritori', LpMaximize)
va = [LpVariable('a%d' % i, upBound=nl, cat=LpBinary) for i in range(na)] # アークを選ぶかどうか
vs = [LpVariable('s%d' % i, lowBound=0, upBound=1) for i in rl] # 先頭かどうか
vp = [LpVariable('p%d' % i, lowBound=0, upBound=nl) for i in rl] # 先頭からの距離
m += lpSum(va)
m += lpSum(vs) == 1
for i in rl:
    so = lpSum(va[j] for j in aout[i])
    si = lpSum(va[j] for j in ain[i]) + vs[i]
    m += so <= si
    m += si <= 1
for i, j, k in arcs:
    m += vp[i] + 1 <= vp[j] + nl * (1 - va[k])
%time m.solve()
print int(value(m.objective) + 1)
p = sum(i * int(value(vs[i])) for i in rl)
while p >= 0:
    print l[p],
    t = -1
    for h in aout[p]:
        i, j, k = arcs[h]
        if value(va[k]) > 0.5:
            t = j
            break
    p = t

コードも短いし、計算も速い(1秒かからず)。

https://codeiq.jp/magazine/2013/08/1710/