개인 노트

A - Rotate

def unite(lst):
    return int("".join(lst))

a, b, c = input()

print(unite([a, b, c]) + unite([b, c, a]) + unite([c, a, b]))

B - Climbing Takahashi

N\leq10^5는 문제 문장에 따라 시뮬레이션을 하더라도 충분히 신속하게 답을 구할 수 있습니다.

N = int(input())
H = list(map(int, input().split()))

H.append(0)
now_h = 0
for i in range(N):
    if H[i] > now_h:
        now_h = H[i]
    else:
        break

print(now_h)

C - The Kth Time Query

Q\leq2\times10^5이기 때문에 각 검색어에서 O(1)로 답을 구하고 싶습니다.
따라서 조회에 대답하기 전에 몇 열의 A를 확인한 다음에 각 숫자가 A의 앞에서 세어 놓은 몇 번째 요소인지 적어두면 된다.
이렇게 되면 사전 확인 시 O(N)에서 각 조회의 처리는 O(1)만 하면 되기 때문에 매우 고속으로 변한다.

from collections import defaultdict

N, Q = map(int, input().split())
A = list(map(int, input().split()))  # 整数を入力

cnt = defaultdict(list)
for i, a in enumerate(A, start=1):
    cnt[a].append(i)

for _ in range(Q):
    x, k = map(int, input().split())
    if len(cnt[x]) < k:
        print(-1)
    else:
        print(cnt[x][k - 1])

D - Multiply and Rotate

칠판에 쓰인 숫자를 정점 BFS로 한다.
두 가지 조작을 통해 칠판의 수 x의 자릿수는 작아지지 않습니다. N<10^6이기 때문에 x가 10^6 미만의 범위 내에서 검색하는 것을 알면 됩니다.
따라서 정점 숫자 N=10^6은 모서리 수가 각 정점부터 2개씩, M=2\times10^6입니다.
BFS는 O(N+M)로 계산되기 때문에 요구 사항이 높을 수 있습니다.

from collections import deque


def append_new_x_after_check():
    if new_x < limit and depth[new_x] == -1:
        depth[new_x] = depth[x] + 1
        queue.append(new_x)


a, N = map(int, input().split())

limit = 10 ** 6
depth = [-1] * (limit + 1)
depth[1] = 0
queue = deque([1])
while queue:
    x = queue.popleft()
    if x == N:
        break

    new_x = x * a
    append_new_x_after_check()

    if x >= 10 and x % 10:
        x_str_lst = list(str(x))
        new_x = int("".join([x_str_lst[-1]] + x_str_lst[:-1]))
        append_new_x_after_check()

print(depth[N])

E - MST + 1

주어진 차트 G의 최소 전역 트리는 단노법를 통해 얻을 수 있습니다.
G의 최소 범위의 나무를 구한 후에 검색어를 처리하는 것을 고려하면 좋은 방법을 모른다.
따라서 단일 프로펠러로 G의 최소 범위 나무를 구할 때도 조회를 통해 얻은 나무를 처리해야 한다.
위키백과에 따라 싱글 프로펠러는 다음 단계로 구성됩니다.

グラフの各頂点がそれぞれの木に属するように、森(木の集合)Fを生成する(つまり頂点1個だけからなる木が頂点の個数だけ存在する)
S ← グラフの全ての辺を含む集合
while (Sが空集合ではない)
    S から重みが最小の辺eを削除する
    if (eが2つの木を連結するもの)
        eを森に加え、2つの木を1つにまとめる

여기서 S는 G의 변뿐만 아니라 조회를 통해 제시된 모든 변도 포함한다.
이렇게 하면while 순환 내의 e는 두 개의 나무를 연결한다. G의 변이 아니라 조회가 주는 변일 때 그 조회의 해는'네'로 변한다.
즉 다음과 같은 절차에 따라 실시된다면

グラフの各頂点がそれぞれの木に属するように、森(木の集合)Fを生成する
S ← グラフの全ての辺とクエリの全ての辺を含む集合
while (Sが空集合ではない)
    Sから重みが最小の辺eを削除する
    if (eが2つの木を連結するもの)
        if (eがGの辺)
            eを森に加え、2つの木を1つにまとめる
        else if (eがクエリの辺)
            eを与えるクエリの解はYes

Union-Find 설치

class UnionFind:
    """Union-Find(素集合データ構造(disjoint-set data structure)に対しての操作)"""

    def __init__(self, n: int):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of node

        Yields
        -----
        root : list
            When value is postive, express root of the node.
            When it is negative, express this node is root and size of set.
        """

        self.root = [-1] * n

    def find(self, x: int) -> int:
        """
        Search root of node x

        Parameters
        ----------
        x : int
            node x

        Returns
        -------
        x : int
            Root of node x
        """

        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def unite(self, x: int, y: int) -> bool:
        """
        Unite two set including node x and node y into one set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        unite_result : bool
            False : Already two node include same set.
            True  : United
        """

        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

    def is_same(self, x: int, y: int) -> bool:
        """
        Determine if x and y are in same set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        result : bool
            Determining result
        """

        return self.find(x) == self.find(y)

    def size(self, x: int) -> int:
        """
        Return size of set including node x.

        Parameters
        ----------
        x : int
            Node number

        Returns
        -------
        Size of set : int
        """

        return self.root[self.find(x)] * -1

N, M, Q = map(int, input().split())
E = []
for _ in range(M):
    a, b, c = map(int, input().split())
    E.append((c, a - 1, b - 1, -1))
for i in range(Q):
    u, v, w = map(int, input().split())
    E.append((w, u - 1, v - 1, i))

E.sort()
ans = [0] * Q
F = UnionFind(N)
for w, a, b, i in E:
    if F.is_same(a, b):
        continue
    if i == -1:
        F.unite(a, b)
    else:
        ans[i] = 1

for is_ok in ans:
    if is_ok:
        print("Yes")
    else:
        print("No")