AtCoderをPythonで取り組んだ振り返り(ABC445 A~C)

どうもこんにちは！

今週は3完、Cまで振り返り。
Dは縦方向または横方向の長さが一致するピースを順にくっつけていくまでは考えたんですが、実装の仕方がよくわからずでした。

問題と公式の解説のリンク

問題は以下のリンクから。

A - Strong Word -

問題

与えられた文字列の先頭と末尾が同じ文字かを判定する問題。

考え方とコード

if文を使って先頭と末尾の文字を比較しました。

s = input()
print("Yes" if s[0] == s[-1] else "No")

B - Center Alignment -

問題

奇数長の文字列がN個与えられます。その中で一番長い文字列にあわせて、短い文字列は前後に.を追加してそろえるという問題。

考え方とコード

ひとまず文字列をすべて受け取って最長の文字列の長さを取得し、その文字列はそのまま出力、それより短い文字列は前後に.を不足分だけ追加して出力するようにしました。

n = int(input())
s = []
m = 0
for _ in range(n):
    tmp = input()
    m = max(m,len(tmp))
    s.append(tmp)

for i in s:
    l = m - len(i)
    print('.' * (l // 2) + i + '.' * (l // 2))

C - Sugoroku Destination -

問題

n個のマスが1列に並んでおり、マス$A_i$にはiからnまでのいずれかの数字が1つ書かれています。マスに駒が置かれているとき、マスに書かれている数字のマスに移動することを繰り返すとしたとき、それぞれのマスから最終的にどのマスで止まるかを出力する問題。
例えばマスが4マスあって各マスには2 3 5 4 5と書かれている場合、各マスから駒に移動を開始した場合最終的には5 5 5 4 5となります。
(なお、問題としては駒の移動を$10^{100}$回行うとしています)

考え方とコード

マス$A_i$にはiからnまでのいずれかの数字が1つ書かれているので、少なくとも1つは以降止まり続けるマスがあります。そこで、各数値ごとに最終地点を保持する辞書を作り、各マスを初期地点として辿っていく際に通った経路を辞書に追加していくことで、残りのマスの計算量を削減しつつ探索する形にしました。

n = int(input())
a = [0] + [int(x) for x in input().split()]
ans = []

# 各数字が行きつく先を保持する辞書
d = {}

for s in range(1,n+1):
    t = a[s]

    # 初期地点の行きつく先が把握できていればそれを答えとして次に進む
    if t in d:
        ans.append(d[t])
        continue

    # 初期地点から最終地点までの経路を取得
    tmp = [t]
    while t != a[t]:
        tmp.append(a[t])
        t = a[t]

    # 出力する答えの保持
    # 経路上の各点からの最終地点の辞書を更新
    ans.append(t)
    for j in tmp:
        d[j] = t

print(*ans)

ではでは。