Atcoder 376 ふりかえり

Atcoder 376回でした。提出したコードとともにふりかえります。PyPy3を利用しています。

B - Hands on Ring (Easy)

import sys

def main():
    N_Q = sys.stdin.readline().split()
    N = int(N_Q[0])
    Q = int(N_Q[1])
    instructions = []
    for _ in range(Q):
        parts = sys.stdin.readline().split()
        H = parts[0]
        T = int(parts[1])
        instructions.append((H, T))
    left = 1
    right = 2
    total_steps = 0
    for H, T in instructions:
        if H == 'L':
            S = left
            O = right
        else:
            S = right
            O = left
        T_i = T
        d_clockwise = (T_i - S + N) % N
        d_to_O_clockwise = (O - S + N) % N
        if 0 < d_to_O_clockwise < d_clockwise:
            steps = (S - T_i + N) % N
        else:
            steps = d_clockwise
        total_steps += steps
        if H == 'L':
            left = T_i
        else:
            right = T_i
    print(total_steps)

if __name__ == "__main__":
    main()

方針

リング上の左右の手の位置を管理しました。
各指示に従って最短移動回数を計算します。
現在の手の位置から目標パーツまでの距離を時計回りと反時計回りで比較し、最小の操作回数を累積します。最後に総操作回数を出力します。

ポイント

• 位置管理: 左右の手の現在位置をleftとrightで追跡。
• 距離計算: 時計回りと反時計回りの距離を(T_i - S + N) % Nで算出。
• 最小操作選択: 最短経路を選び、操作回数を累積。
• 効率性: 各指示をO(1)で処理し、全体でO(Q)の計算量。

C - Prepare Another Box　

import sys
import bisect

def main():
    N_and_rest = sys.stdin.read().split()
    N = int(N_and_rest[0])
    A = list(map(int, N_and_rest[1:N+1]))
    B = list(map(int, N_and_rest[N+1:]))
    A_sorted = sorted(A, reverse=True)
    B_sorted = sorted(B, reverse=True)
    
    def is_possible(x):
        boxes = B_sorted.copy()
        bisect.insort(boxes, x)
        boxes_sorted = sorted(boxes, reverse=True)
        for i in range(N):
            if i >= len(boxes_sorted):
                return False
            if A_sorted[i] > boxes_sorted[i]:
                return False
        return True
    
    left = 1
    right = 10**10
    answer = -1
    while left <= right:
        mid = (left + right) // 2
        if is_possible(mid):
            answer = mid
            right = mid -1
        else:
            left = mid +1
    print(answer)

if __name__ == "__main__":
    main()

方針

二分探索を用いて、追加する箱の最小サイズ x を効率的に求めます。まず、おもちゃと既存の箱を大きさ順に降順ソートし、各二分探索のステップで x を挿入後、全てのおもちゃが適切な箱に収まるかを確認します。条件を満たす最小の x を見つけることで、高橋君が操作2を実行可能にします。

ポイント

• 二分探索の活用: 最小の x を効率的に探索するために二分探索を採用。
• ソートによる効率化: おもちゃと箱を降順にソートし、比較を簡略化。
• bisectモジュールの利用: 挿入位置を高速に特定するために bisect.insort を使用。
• 計算量の最適化: ソートと二分探索により、全体の計算量を O(N log N) に抑制。

D - Cycle

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    adj = [[] for _ in range(N+1)]
    to1 = []
    index = 2
    for _ in range(M):
        a = int(data[index])
        b = int(data[index+1])
        adj[a].append(b)
        if b == 1:
            to1.append(a)
        index += 2
    distance = [-1]*(N+1)
    distance[1] = 0
    q = deque([1])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if distance[v] == -1:
                distance[v] = distance[u] +1
                q.append(v)
    min_cycle = float('inf')
    for u in to1:
        if distance[u] != -1:
            min_cycle = min(min_cycle, distance[u] +1)
    print(min_cycle if min_cycle != float('inf') else -1)

if __name__ == "__main__":
    main()

方針

BFSを用いて頂点1から各頂点への最短距離を計算。頂点1に戻る辺を探索し、閉路を形成する最小の辺数を求めます。存在しない場合は-1を出力します。

ポイント

• BFSによる効率的な探索：広がり優先で最短距離を計算。
• 閉路検出：頂点1に戻る辺を利用して閉路を形成。
• 隣接リストの活用：大規模グラフにも対応可能なデータ構造。
• 計算量の最適化：O(N + M)で高速に処理。