丸紅プログラミングコンテスト2024（AtCoder Regular Contest 183）A,B,C,D問題メモ

from itertools import permutations


def bruteforce(n, k):
    a = []
    for i in range(1, n + 1):
        a.extend([i] * k)
    print(a)
    aaa = set(permutations(a))
    aaa = sorted(aaa)
    for i, a in enumerate(aaa):
        print(i, a)
    s = len(aaa)
    print((s + 1) // 2 - 1)
    print(aaa[(s + 1) // 2 - 1])


n, k = map(int, input().split())
# bruteforce(n, k)

if n == 1:
    ans = [n] * k
    print(*ans)
    exit()

m = (n + 1) // 2
if n % 2 == 0:
    ans = [m]
    for i in range(n, 0, -1):
        if i == m:
            ans.extend([i] * (k - 1))
        else:
            ans.extend([i] * k)
else:
    ans = [m] * k
    ans.append(m - 1)
    for i in range(n, 0, -1):
        if i == m:
            pass
        elif i == m - 1:
            ans.extend([i] * (k - 1))
        else:
            ans.extend([i] * k)

print(*ans)

from collections import defaultdict
from operator import itemgetter

from more_itertools.more import run_length


def solve(n, k, aaa, bbb):
    if k == 1:
        rla = list(map(itemgetter(0), run_length.encode(aaa)))
        rlb = list(map(itemgetter(0), run_length.encode(bbb)))
        m = len(rlb)
        j = 0
        for a in rla:
            if rlb[j] == a:
                j += 1
                if j == m:
                    return True
        return False

    if aaa == bbb:
        return True

    if set(bbb) - set(aaa):
        return False

    last_appear = defaultdict(lambda: -1000_000_000)
    for i, b in enumerate(bbb):
        la = last_appear[b]
        if i - la <= k:
            return True
        last_appear[b] = i

    return False


t = int(input())
buf = []
for _ in range(t):
    n, k = map(int, input().split())
    aaa = list(map(int, input().split()))
    bbb = list(map(int, input().split()))
    if solve(n, k, aaa, bbb):
        buf.append('Yes')
    else:
        buf.append('No')
print('\n'.join(buf))

def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


MOD = 998244353
n, m = map(int, input().split())
banned = [[0] * (n + 1) for _ in range(n)]
for _ in range(m):
    l, r, x = map(int, input().split())
    l -= 1
    x -= 1
    banned[l][r] |= 1 << x
facts, finvs = precompute_factorials(n, MOD)

for i in range(n - 1, 0, -1):
    for j in range(n + 1):
        banned[i - 1][j] |= banned[i][j]
for j in range(n):
    for i in range(n):
        banned[i][j + 1] |= banned[i][j]

dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    if banned[i][i + 1] == 0:
        dp[i][i + 1] = 1
    dp[i][i] = 1
dp[n][n] = 1

for w in range(2, n + 1):
    comb = []
    for i in range(w):
        comb.append(facts[w - 1] * finvs[i] * finvs[w - 1 - i] % MOD)
    for l in range(n - w + 1):
        r = l + w
        bitset = banned[l][r]
        tmp = 0
        for m in range(l, r):
            if bitset >> m & 1:
                continue
            tmp += dp[l][m] * dp[m + 1][r] * comb[m - l]
            tmp %= MOD
        dp[l][r] = tmp

ans = dp[0][n]
print(ans)

• F - Perfect Matching on a Tree

from collections import defaultdict
from heapq import heapify, heappop, heappush
from typing import Iterable, List, Set, Optional, Dict, Tuple


def get_centroid(n: int, links: List[Iterable[int]], s: int, removed: Optional[Set[int]] = None) \
        -> Tuple[List[int], Dict[int, int]]:
    """
    木の重心を見つける。
    重心は1つまたは2つあるため、リストで返す。また、s を根とした際の部分木のサイズも返す。

    繰り返し重心分解する場合にも適用可能。
    removedには既に重心として確定された頂点集合を与え、そこにある頂点は探索されないようになる。
    n には木全体ではなく、探索範囲の頂点数を与える。（1回前に探索した部分木のサイズから計算できる）

    :param n: 木の（探索範囲の）頂点数
    :param links: 隣接リスト
    :param s: 探索開始頂点
    :param removed: 探索しない頂点集合
    :return:
    """
    if removed is None:
        removed = set()

    parents = {s: -1}
    subtree_sizes = {s: n}
    status = defaultdict(int)
    q = [s]
    limit = n // 2
    centroid = []
    while q:
        u = q[-1]
        if status[u] == 0:
            status[u] = 1
            for v in links[u]:
                if parents[u] == v:
                    continue
                if v in removed:
                    continue
                parents[v] = u
                q.append(v)
        else:
            status[u] = 2
            q.pop()
            my = 1
            is_centroid = True
            for v in links[u]:
                if status[v] != 2:
                    continue
                if v in removed:
                    continue
                scv = subtree_sizes[v]
                my += scv
                if scv > limit:
                    is_centroid = False
            subtree_sizes[u] = my
            if n - my > limit:
                is_centroid = False
            if is_centroid:
                centroid.append(u)
    return centroid, subtree_sizes


def get_subtree_sizes(n, links, s):
    """ s を根とした部分木サイズを構築する。ついでに links から親頂点を削除する """
    subtree_sizes = [-1] * n
    depths = [-1] * n
    depths[s] = 0
    q = [s]
    while q:
        u = q[-1]
        dv = depths[u] + 1
        if subtree_sizes[u] == -1:
            subtree_sizes[u] = -2
            p = -1
            for v in links[u]:
                if subtree_sizes[v] == -1:
                    q.append(v)
                    depths[v] = dv
                else:
                    p = v
            if p != -1:
                links[u].remove(p)
        else:
            q.pop()
            tmp = 1
            for v in links[u]:
                if subtree_sizes[v] >= 0:
                    tmp += subtree_sizes[v]
            subtree_sizes[u] = tmp
    return subtree_sizes, depths


def build_post_order(links: List[List[int]], s: int):
    """
    s からオイラーツアーし、帰りがけ順の頂点列を構築する。
    links[u] = [v1, v2, ...] は、隣接頂点をリストで持つ。この順に訪れる。

    links には、親頂点は入っていない前提とする。
    """
    result = []
    visited = set()
    q = [s]
    while q:
        u = q[-1]
        if u not in visited:
            q.extend(reversed(links[u]))
            visited.add(u)
        else:
            q.pop()
            result.append(u)
    return result



def solve(n, links):
    centroids, _ = get_centroid(n, links, 0)
    cen = centroids[0]

    # 部分木サイズ・深さを計算、linksから親頂点を除く
    subtree_sizes, depths = get_subtree_sizes(n, links, cen)

    # 奇数サイズの子が1番目に来るように、linksの並び順を加工
    links2 = []
    for i in range(n):
        links2.append(sorted(links[i], key=lambda v: subtree_sizes[v] % 2, reverse=True))
    links = links2

    root_children = links[cen]
    rtch_cnt = len(root_children)
    odd_queue = []
    even_queue = []
    post_orders = []
    for i in range(rtch_cnt):
        ch = root_children[i]
        post_order = build_post_order(links, ch)
        post_order.reverse()  # pop で取り出すため逆順にする
        post_orders.append(post_order)
        if depths[post_order[-1]] % 2 == 0:
            even_queue.append((-len(post_order), i))
        else:
            odd_queue.append((-len(post_order), i))
    heapify(even_queue)
    heapify(odd_queue)

    ans = []
    for _ in range(n // 2 - 1):
        _, i = heappop(even_queue)
        _, j = heappop(odd_queue)
        poi = post_orders[i]
        poj = post_orders[j]
        u = poi.pop()
        v = poj.pop()
        ans.append(f'{u + 1} {v + 1}')

        if poi:
            if depths[poi[-1]] % 2 == 0:
                heappush(even_queue, (-len(poi), i))
            else:
                heappush(odd_queue, (-len(poi), i))
        if poj:
            if depths[poj[-1]] % 2 == 0:
                heappush(even_queue, (-len(poj), j))
            else:
                heappush(odd_queue, (-len(poj), j))

    _, i = odd_queue[0]
    poi = post_orders[i]
    v = poi.pop()
    ans.append(f'{v + 1} {cen + 1}')
    return ans


n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)
ans = solve(n, links)
print('\n'.join(ans))