ABC320(A~D)をPythonで解く

初めに

ABC320のA~D問題をPythonで解きました。

A: Leyland Number

xのy乗はx**yで計算できます。

コード

A, B = map(int, input().split())
print(A**B+B**A)

B: Longest Palindrome

Sの制約が小さいので部分文字列の初めと終わりで全探索しても間に合います。

文字列sの回文判定は、文字列を左右反転させたものs[::-1]とsが一致するかどうかで可能です。

また、長さ一文字の部分文字列は常に回文です。

コード

S = input()
ans = 1
for start in range(len(S)):
    for end in range(start+1, len(S)+1):
        s = S[start:end]
        if s == s[::-1]:
            ans = max(ans, len(s))

print(ans)

C: Slot Strategy

制約が100と小さいので三つのリールを全探索しても$O(N^3)$で間に合います。

t秒目に押せるボタンは一つなので、リールを止めるタイミングは別々である必要があります。

三つのリールにおいて共通する数字が同じ位置にしか存在しない場合はスロットが3周する必要があるので、事前に全てのリールを3倍にしておきます。

それぞれのリールの組み合わせにおいて、数字が一致するか、そしてタイミングが別々か確認します。ボタンを押す最後のタイミングを更新してそのうちの最小を求めます。

コード

M = int(input())
s1 = input()*3
s2 = input()*3
s3 = input()*3

cnt = 10**18

for f in range(M*3):
    for s in range(M*3):
        for t in range(M*3):
            if (s1[f]==s2[s]==s3[t]) and (f!=s and f!=t and s!=t):
                cnt = min(cnt, max(f,s,t))


print(cnt if cnt < 10**18 else -1)

D: Relative Position

座標が一意に定まるのは、座標がすでに定まっている点から観測された時です。なので座標１から観測できる点をすべて定め、定まった点から観測できる点を同様にすべて定め、の繰り返しで可能なすべての点を定めることができます。

これは点１から始める幅優先探索(BFS)で実行できます。

観測は双方向で可能なことに注意します。具体的には、点1から点2がx軸正方向に3, y軸正方向に4離れているとき、点2から点1はx軸正方向に-3, y軸正方向に-4離れています。

コード

from collections import deque

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    INF = 10**9+1

    for _ in range(M):
        a, b, x, y = map(int, input().split())
        # 双方向の観測
        graph[a].append([b, x, y])
        graph[b].append([a, -x, -y])

    def bfs(g):
        
        # 各点の座標
        cord = [(INF, INF) for _ in range(N+1)]
        # すでに座標が定まっているかどうか
        seen = [(False) for _ in range(N+1)]
        # 原点よりスタート
        cord[1] = (0, 0)
        seen[1] = True

        #　キューを作成して原点(点,x座標, y座標)を追加します
        que = deque([])
        que.append((1, 0, 0))

        while que:
            v, x, y = que.popleft()
            seen[v] = True
            # 点ｖより観測可能な点の座標を定めます
            for next_v, nx, ny in g[v]:
                if seen[next_v]: continue 
                cord[next_v] = (x+nx, y+ny)
                que.append((next_v, x+nx, y+ny))
    
    bfs(graph)

    for i in range(1, N+1):
        x, y = cord[i]
        if x == y == INF:
            print("undecidable")
        else:
            print(x, y)

main()