【競技プログラミング】AtCoder Beginner Contest 372_E問題

問題

既存投稿一覧ページへのリンク

一覧ページ

解法手順1

1. Union-Find（素集合データ構造）の利用

• 頂点同士が連結されるたびに、それらを同じグループとして管理する。
• グループ管理にはUnion-Find（素集合データ構造）を使う。

2. 各グループ内で頂点番号を管理

• 各グループごとに、所属する頂点番号を降順でリストとして保持。
• マージ時には2つのグループのリストを結合し、降順ソートして上位10個だけ保持。

3. クエリ処理

• タイプ1 (辺追加)：

  • 頂点 $ u $ と頂点 $ v $ を連結。
  • Union-Findでそれぞれのrootを求め、異なる場合はマージ処理を行う。

• タイプ2 (クエリ)：

  • 頂点 $ v $ の属するグループについて、そのグループ内で頂点番号が大きい順に並べたときの $ k $ 番目の頂点番号を出力。
  • グループサイズが $ k $ 未満の場合は -1 を出力。

処理フローまとめ

1. 入力受け取り (io_func)
   • 頂点数 $ N $、クエリ数 $ Q $、および各クエリ情報を取得。
2. 初期化 (solve)
   • Union-Find構造体 (UnionFind) を初期化。
3. クエリ処理 (solve内)
   • クエリタイプごとに以下の処理：
     • タイプ1：Union-Findでマージ処理。
     • タイプ2：該当するグループからk番目に大きい頂点番号または -1 を出力。

ACコード1

ac.py

import logging

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')

        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)

    logger.debug(f"ロガーのセットアップが完了しました。デバッグモード: {debug_mode}")
    return logger

class UnionFind:
    def __init__(self, n, logger):
        self.par = [-1 for _ in range(n)]
        self.comp = [[i] for i in range(n)]
        self.logger = logger
        self.logger.debug(f"UnionFindを初期化しました。頂点数: {n}")

    def root(self, v):
        if self.par[v] < 0:
            return v
        else:
            self.par[v] = self.root(self.par[v])
            return self.par[v]

    def size(self, v):
        return -self.par[self.root(v)]

    def merge(self, u, v):
        u_root = self.root(u)
        v_root = self.root(v)
        if u_root == v_root:
            self.logger.debug(f"頂点{u}と頂点{v}は既に同じグループです。")
            return
        if self.size(u_root) > self.size(v_root):
            u_root, v_root = v_root, u_root

        # u_root を v_root にマージする
        self.comp[v_root] += self.comp[u_root]
        self.comp[u_root] = []
        self.comp[v_root].sort(reverse=True)
        self.comp[v_root] = self.comp[v_root][:10]

        # 親の更新処理
        self.par[v_root] += self.par[u_root]
        self.par[u_root] = v_root

        self.logger.debug(f"頂点{u}の属するグループを頂点{v}の属するグループにマージしました。")

def io_func():
    N, Q = map(int, input().split())
    queries = [list(map(int, input().split())) for _ in range(Q)]
    return N, Q, queries

def solve(N, Q, queries, logger):
    uf = UnionFind(N + 1, logger)
    for query in queries:
        if query[0] == 1:
            _, u, v = query
            uf.merge(u, v)
            logger.debug(f"クエリタイプ1: 頂点{u}と頂点{v}を接続しました。")
        else:
            _, v, k = query
            root_v = uf.root(v)
            comp_size = len(uf.comp[root_v])
            if comp_size < k:
                print(-1)
                logger.debug(f"クエリタイプ2: 頂点{v}の属するグループのサイズが{k}未満({comp_size})のため、-1を出力しました。")
            else:
                result = uf.comp[root_v][k - 1]
                print(result)
                logger.debug(f"クエリタイプ2: 頂点{v}の属するグループで{k}番目に大きい番号は{result}です。")

def main():
    debug_mode = False
    logger = setup_logger(debug_mode)
    N, Q, queries = io_func()
    solve(N, Q, queries, logger)

if __name__ == "__main__":
    main()