🙌

AtCoder ABC218 個人的メモ

2021/09/12に公開

Python

競技プログラミング

AtCoder

tech

A - Weather Forecast

N = int(input())
S = input()

if S[N - 1] == "o":
    print("Yes")
else:
    print("No")

B - qwerty

from string import ascii_lowercase

P = list(map(int, input().split()))

# string.ascii_lowercaseは英小文字がアルファベット順に列挙された文字列
lst = ascii_lowercase
ans = [lst[p - 1] for p in P]
print("".join(ans))

C - Shapes

問題文通りシミュレーションすれば良さそう
でも実装がめんどくさい

公式解説の $O(N^3)$ 解法と一緒

↓の実装では使えないがリストの回転は↑の様にやると楽そう

from itertools import product

N = int(input())
S = [input() for _ in range(N)]
T = [input() for _ in range(N)]

# S,Tのそれぞれの"#"マスの座標をメモする
S_blacks = []
T_blacks = set()
for i in range(N):
    for j in range(N):
        if S[i][j] == "#":
            S_blacks.append((i, j))
        if T[i][j] == "#":
            T_blacks.add((i, j))

# SとTで"#"の個数が異なる場合は明らかに一致しない
if len(T_blacks) != len(S_blacks):
    print("No")
    exit()

for _ in range(4):
    # 平行移動
    for di, dj in product(range(-N, N + 1), repeat=2):
        if all((i + di, j + dj) in T_blacks for i, j in S_blacks):
            print("Yes")
            exit()

    # Sの"#"の座標を90度回転
    new_s = []
    for i, j in S_blacks:
        new_s.append((j, N - 1 - i))
    S_blacks = list(new_s)

print("No")

D - Rectangles

x座標が同じ2つの点a,bを選ぶ。
残る2点c,dは以下の2つの条件を満たせばおｋ。

cとdのx座標が等しい
aとc,bとdのy座標が等しい

よって、上記を満たす組み合わせを数えればおｋ。
これは各点をx座標ごとに1まとめにしておくと楽に求められる。

from collections import defaultdict
from itertools import combinations

N = int(input())
# 各点をx座標ごとにyの座標をメモ
x_key_y_set = defaultdict(set)
for _ in range(N):
    x, y = map(int, input().split())
    x_key_y_set[x].add(y)

keys = list(x_key_y_set.keys())
ans = 0
for i, x1 in enumerate(keys):
    # 同じx座標を持つ2点を選ぶ((a,b)はその2点のy座標)
    for a, b in combinations(x_key_y_set[x1], 2):
        # 同一の4点の組み合わせを重複して数える事を避けつつ数える
        for x2 in keys[i + 1:]:
            if a in x_key_y_set[x2] and b in x_key_y_set[x2]:
                ans += 1

print(ans)

E - Destruction

報酬が最大値になる場合は削除可能かつ $C_i$ が正の辺を全て取り除いた場合。
なので、残すグラフはできるだけ $C_i$ が小さい辺で構成されている連結グラフになる。
これは最小全域木なので、プリム法をやればおｋ。

from heapq import heappop, heappush

N, M = map(int, input().split())
C = []
edge = [[] for _ in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append((c, b, i))
    edge[b].append((c, a, i))
    C.append(c)

# プリム法の準備
priority_queue = []      # 頂点0(問題文では頂点1)を端点とする辺を優先度付きキューに入れる
for c, n_node, i in edge[0]:
    heappush(priority_queue, (c, n_node, i))
seen = [0] * N           # 頂点iが到達済みか？をメモ
seen[0] = 1
need_edge = [0] * M      # 辺iが最小全域木に必要か？をメモ
num_remain_node = N - 1  # 未到達の頂点数をメモ
# プリム法
while num_remain_node:
    _, now, i = heappop(priority_queue)
    if seen[now]:
        continue
    seen[now] = 1
    need_edge[i] = 1
    num_remain_node -= 1

    for c, n_node, j in edge[now]:
        if seen[n_node]:
            continue
        heappush(priority_queue, (c, n_node, j))

ans = 0
for i, is_need in enumerate(need_edge):
    if is_need or C[i] < 0:
        continue
    ans += C[i]

print(ans)

参考

F - Blocked Roads

from collections import deque


def bfs(remove_edge_i: int = -1):
    """
    辺iが通れないときの頂点1から頂点Nへの最短経路をbfsで求めて、通過した辺のリストを返す。
    頂点Nに到達できなかった場合はFalseを返す。
    引数が無いときは全ての辺を通れる。
    """
    queue = deque([0])
    # 頂点iにどの辺を通ってやって来たかをメモ(後で経路復元する)
    migration = [-1] * N
    while queue:
        now = queue.popleft()

        if now == N - 1:
            return route_restore(migration)

        for n_node, j in edge[now]:
            if migration[n_node] != -1 or j == remove_edge_i:
                continue
            queue.append(n_node)
            migration[n_node] = j

    return False


def route_restore(lst: list):
    """
    ↑の関数で求めたmigrationから経路復元する。
    """
    res = []
    now = N - 1
    while now:
        next_edge = lst[now]
        res.append(next_edge)
        now = ST[next_edge][0]
    return res


N, M = map(int, input().split())
ST = [list(map(lambda n: int(n) - 1, input().split())) for _ in range(M)]
edge = [[] for _ in range(N)]
for i, (x, y) in enumerate(ST):
    edge[x].append((y, i))

# 全ての辺が通れる状態での最短経路を探索
best_path = bfs()

# 全ての辺が通れる状態で頂点Nに到達不可能な場合
if not best_path:
    print(*(-1 for _ in range(M)), sep="\n")
    exit()

ans = [len(best_path)] * M
# 最短経路を構成している各辺それぞれが除去された場合の最短経路を探索
for i in best_path:
    tmp_path = bfs(i)
    if tmp_path:
        ans[i] = len(tmp_path)
    else:
        ans[i] = -1

print(*ans, sep="\n")