【今日の精進】ABC175F - Making Palindrome

毎日格上の問題を倒すやつの71日目です。

問題リンク

atcoder.jp

問題概要

個の文字列があり、 個目の文字列 はコスト かかるよ。

回文を作るための最小コストを求めてね。

解法

両端から作っていきます。

すると、「回文ができる」か、「片方が対消滅し、部分文字列が残る」のどちらかになります。

そして、残る部分文字列の個数は なので、この上でダイクストラすればよいです。

提出コード

from heapq import heappop,heappush

INF=pow(2,61)-1
N=int(input())
S=[]
for i in range(N):
    s,c=input().split()
    c=int(c)
    S.append((s,c))
vert=[(0,0,0)]
dist=[[INF]*45 for i in range(N)]
dist[0][0]=0
ans=INF
while len(vert)>0:
    dis,pos,le=heappop(vert)
    if dist[pos][le]!=dis:
        continue
    if le>=0:
        now=S[pos][0][:le]
    else:
        now=S[pos][0][le:]
    cnt=0
    for s,c in S:
        if le>=0:
            if s+now==(s+now)[::-1]:
                ans=min(ans,dis+c)
            else:
                if len(s)<len(now):
                    if now[-len(s):]==s[::-1]:
                        if dist[pos][le-len(s)]>dis+c:
                            dist[pos][le-len(s)]=dis+c
                            heappush(vert,(dis+c,pos,le-len(s)))
                else:
                    if s[:len(now)]==now[::-1]:
                        if dist[cnt][le-len(s)]>dis+c:
                            dist[cnt][le-len(s)]=dis+c
                            heappush(vert,(dis+c,cnt,le-len(s)))
        else:
            if now+s==(now+s)[::-1]:
                ans=min(ans,dis+c)
            else:
                if len(s)<len(now):
                    if now[:len(s)]==s[::-1]:
                        if dist[pos][le+len(s)]>dis+c:
                            dist[pos][le+len(s)]=dis+c
                            heappush(vert,(dis+c,pos,le+len(s)))
                else:
                    if s[-len(now):]==now[::-1]:
                        if dist[cnt][le+len(s)]>dis+c:
                            dist[cnt][le+len(s)]=dis+c
                            heappush(vert,(dis+c,cnt,le+len(s)))
        cnt+=1
if ans>=INF:
    print(-1)
else:
    print(ans)

Submission #48040882 - AtCoder Beginner Contest 175

感想

良問のにおい