完璧主義者脱却への道のり！ 2025/02/23

はじめに

完璧主義者脱却のための日記&学習記録，9日目です．
今日もゆる～く書いていきます．

にっき

今日は大学の友達(自称おもしれー女)と通話して世間話をしたりしました．その会話の中でいろんな噂話(?)を聞いたのですが，そんな話一体どこで仕入れているんだという感じになりましたが，結論としては僕に友達がいなさすぎるということになりました．自分でもうすうすそんな気はしていたのですが，人にそう思われていると知ると来るものがありますね...

まなんだこと

今日は1日ダラダラしてしまっていたので，昨日のAtCoderの問題を解いてみました．

グラフ上の回文を探すという趣旨の問題でした．

方針としては，ある回文の両端に同じ文字をつけて回文にしていく操作を繰り返すことで，回文を作ってその両端を結ぶパスとしていきます．
これを幅優先探索をしながら値を更新することで答えを出すことができるはずです．

解答コード

from collections import deque

n = int(input())

invar = [[[] for _ in range(26)] for _ in range(n)]
outvar = [[[] for _ in range(26)] for _ in range(n)]

for i in range(n):
    c = list(input())
    for j in range(n):
        if c[j] != "-":
            invar[j][ord(c[j]) - ord("a")].append(i)
            outvar[i][ord(c[j]) - ord("a")].append(j)


queue = deque()
ans = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    # 頂点 i が中心
    queue.append((i, i, 0))
    ans[i][i] = 0

for i in range(n):
    for a in range(26):
        for j in outvar[i][a]:
            # 辺 i->j が中心
            if ans[i][j] == -1 or 1 < ans[i][j]:
                queue.append((i, j, 1))
                ans[i][j] = 1

while queue:
    s, t, m = queue.popleft()
    for a in range(26):
        for k in invar[s][a]:
            for j in outvar[t][a]:
                if ans[k][j] == -1 or m + 2 < ans[k][j]:
                    queue.append((k, j, m + 2))
                    ans[k][j] = m + 2

for i in range(n):
    print(*ans[i])

おわりに

今日は1日ダラダラしてしまいました．
明日も1日休んで，火曜日からのバイトに備えたいと思います．