AtCoder ABC235 個人的メモ

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\leq 10^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\leq 2\times 10^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。
2つの操作によって黒板の数$x$の桁が小さくなることは無く、$N<10^6$であるので、$x$は$10^6$未満の範囲で探索すれば良いと分かる。
よって頂点数$N=10^6$、辺の数が各頂点から2つずつで$M=2\times 10^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$の最小全域木をクラスカル法で求める時に、クエリで与えられる辺も処理することにする。
クラスカル法はWikipediaによると、以下の手順からなる。

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

ここで$S$に$G$の辺だけでなく、クエリで与えられる全ての辺も含めておく。
こうすればwhileループ内での$e$が、2つの木を連結するものであり、$G$の辺ではなくクエリで与えられた辺である時、そのクエリの解はYesになる。
つまり、以下の手順で実装すればおｋ

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

Uinon-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")