ABC445をPythonで

AtCoder Beginner Contest 445の解答等の速報的まとめ

A問題

そのまま

A

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

B問題

最大文字数を調べる。
その後、各文字列と最大文字数の差の半分だけ.を前後につける

B

n = int(input())
data = list()
max_len = 0
for _ in range(n):
    s = input()
    max_len = max(max_len, len(s))
    data.append(s)

for s_i in data:
    k = (max_len - len(s_i)) // 2
    print("." * k + s_i + "."* k)

C問題

サイクルを調べ、そこまでの距離とサイクルの長さから求める

ちなみに、$i \le a_i$の条件を見落としていた

C

def get_cycle(edge):
    n = len(edge)
    cycle_id = [0] * n  # どのサイクルに属するか
    cycle_pos = [0] * n  # サイクル内での位置
    cycle_dict = {}  # 各サイクルの要素

    visited = [False] * n
    current_cycle = 0

    for start in range(n):
        if visited[start]:
            continue

        # このstartから到達可能な全ての点を探索
        path = []
        pos = start

        while not visited[pos]:
            path.append(pos)
            visited[pos] = True
            pos = edge[pos]

        if cycle_id[pos] != 0:
            for i, p in enumerate(path):
                cycle_id[p] = cycle_id[pos]
                cycle_pos[p] = -1
        else:
            current_cycle += 1

            cycle_start_idx = path.index(pos)
            cycle_dict[current_cycle] = path[cycle_start_idx:]

            for i in range(cycle_start_idx):
                cycle_id[path[i]] = current_cycle
                cycle_pos[path[i]] = -1

            for i in range(cycle_start_idx, len(path)):
                cycle_id[path[i]] = current_cycle
                cycle_pos[path[i]] = i - cycle_start_idx
    return cycle_id, cycle_pos, cycle_dict


n = int(input())
a = [int(x) - 1 for x in input().split()]

cy_id, cy_pos, cy_dict = get_cycle(a)

cycle_start = [-1] * n
for now in range(n):
    dist = 0
    if cycle_start[now] == -1:
        lst = list()
        while cy_pos[now] == -1:
            lst.append(now)
            now = a[now]
            dist += 1
        for l_i in lst:
            cycle_start[l_i] = now
    else:
        now = cycle_start[now]

    cycle_ind = cy_id[now]
    cycle = cy_dict[cycle_ind]
    cycle_len = len(cycle)
    step = (10 ** 100 - dist) % cycle_len

    ans = cycle[(cy_pos[now] + step) % cycle_len]

    print(ans + 1, end=" ")

D問題

問題文の条件から、縦か横の長さが一致するものから順にとれる

D

def ans_add(key, i, j):
    global ans_dict
    if key not in ans_dict:
        ans_dict[key] = list()
    ans_dict[key].append((i, j))


h, w, n = map(int, input().split())
data = [tuple(map(int, input().split())) for _ in range(n)]

all_count = dict()
for h_i, w_i in data:
    key = (h_i, w_i)
    if key not in all_count:
        all_count[key] = 0
    all_count[key] += 1

h_sort = sorted(data)
w_sort = sorted(data, key=lambda x:(x[1], x[0]))

ans_dict = dict()
used = dict()
ans_count = 0
x, y = h, w
while ans_count < n:
    while h_sort:# 重複削除
        key_h = h_sort[-1]
        if key_h in used and all_count[key_h] == used[key_h]:
            h_sort.pop()
        else:
            break
    while w_sort:
        key_w = w_sort[-1]
        if key_w in used and all_count[key_w] == used[key_w]:
            w_sort.pop()
        else:
            break

    if h_sort[-1][0] == x:
        h_i, w_i = h_sort.pop()
        new_y = y - w_i
        ans_add((h_i, w_i), 1, new_y + 1)
        y = new_y
    else:
        h_i, w_i = w_sort.pop()
        new_x = x - h_i
        ans_add((h_i, w_i), new_x + 1, 1)
        x = new_x

    if (h_i, w_i) not in used:
        used[(h_i, w_i)] = 0
    used[(h_i, w_i)] += 1
    ans_count += 1

for h_i, w_i in data:
    ans = ans_dict[(h_i, w_i)].pop()
    print(*ans)