キーサイト・テクノロジープログラミングコンテスト（AtCoder Beginner Contest 454）E,F,G問題メモ

def solve(n, a, b):
    if n % 2 == 1:
        return None
    if (a + b) % 2 == 0:
        return None

    if a + b > n + 1:
        ans = solve(n, n - a + 1, n - b + 1)
        ans = ans[::-1]
        # return ans.translate(str.maketrans({'U': 'D', 'D': 'U', 'L': 'R', 'R': 'L'}))
        return ans

    if a > b:
        move = [
            [('L', 0, -1), ('D', 1, 0), ('R', 0, 1)],
            [('L', 0, -1), ('U', -1, 0), ('R', 0, 1)],
        ]

        def switcher(i, j):
            nonlocal mi
            if mi == 0 and i == n:
                mi ^= 1
            elif mi == 1 and i == 1:
                mi ^= 1
    else:
        move = [
            [('U', -1, 0), ('R', 0, 1), ('D', 1, 0)],
            [('U', -1, 0), ('L', 0, -1), ('D', 1, 0)],
        ]

        def switcher(i, j):
            nonlocal mi
            if mi == 0 and j == n:
                mi ^= 1
            elif mi == 1 and j == 1:
                mi ^= 1

    mi = 0

    moved = [[False] * (n + 2) for _ in range(n + 2)]
    for i in range(n + 2):
        moved[0][i] = moved[i][0] = moved[-1][i] = moved[i][-1] = True
    i, j = 1, 1
    moved[1][1] = True
    moved[a][b] = True
    ans = []
    while i != n or j != n:
        for c, di, dj in move[mi]:
            ni = i + di
            nj = j + dj
            if moved[ni][nj] == False:
                ans.append(c)
                moved[ni][nj] = True
                i = ni
                j = nj
                break
        else:
            raise AssertionError
        switcher(i, j)
    # assert len(ans) == n * n - 2
    return ''.join(ans)

t = int(input())
for _ in range(t):
    n, a, b = list(map(int, input().split()))
    ans = solve(n, a, b)
    if ans is not None:
        print('Yes')
        print(ans)
    else:
        print('No')

ある数列 $X$ に対し、「$f(X):=X_i$ のうち正の要素のみの和」とする。

以下の2条件を満たす既存の $X$ があるとする。

• $\sum X = 0$
• $X_i \equiv D_i \mod{M}$

同じ2条件を満たす $X$ 以外の数列は、$\mod{M}$ を変えてはいけないので「2つの位置 $i,j$ を選び、$X_i$ に $+M$、$X_j$ に $-M$ する」 操作を繰り返すことでのみ作れる。

$X_i$ が正の時、$j$ に関わらず、$f(X)$ が減少することはない。
（$f(X)$ は、$X_i$ に $M$ を加算した時点で確実に $M$ 増える。$-M$ によって減少するのは最大でも $M$ である）

$X_j$ が負の時も、同様の議論により $f(X)$ が減少することはない。

よって、$f(X) \gt f(Y)$ となるような $Y$ があるなら $X_i \lt 0$、$X_j \gt 0$ しかないが、 これも、$D_i$ が大きなものから負にした以上、$X_i \le X_j+M$ なので、改善することはない。

def solve(n, m, aaa):
    if n == 1:
        return 0

    bbb = []
    for i in range(n // 2):
        bbb.append((aaa[n - i - 1] - aaa[i]) % m)
    bbb.append(0)

    prev = 0
    ddd = []
    for b in bbb:
        d = (b - prev) % m
        ddd.append(d)
        prev = b

    ddd.sort(reverse=True)
    s = sum(ddd)
    k = s // m
    ans = sum(ddd[k:])
    return ans


t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    aaa = list(map(int, input().split()))
    ans = solve(n, m, aaa)
    print(ans)

def decode_input(n, seed, m, f, qqq, ddd):
    state = seed

    parents = [-1] * n
    children = [[] for _ in range(n)]
    mask = (1 << 31) - 1
    for i in range(1, n):
        if i < m:
            p = qqq[i - 1] - 1
            parents[i] = p
            children[p].append(i)
        else:
            p = state % i
            parents[i] = p
            children[p].append(i)
            state = (state * 1103515245 + 12345) & mask

    colors = [0] * n
    for i in range(n):
        if i < m:
            colors[i] = ddd[i] - 1
        else:
            colors[i] = state % f
            state = (state * 1103515245 + 12345) & mask

    return parents, children, colors


class DsuOnTree:
    """
    https://speakerdeck.com/camypaper/dsu-on-tree

    木でのマージテクを定数倍高速におこなう技。
    subtree の状態を管理する1つの配列を全体で使い回し、Dictなどの重ための構造を何度も生成するのを避ける。

    データの持たせ方が問題毎に様々あり、共通化しづらいため、ある程度は呼び出し側で管理し、カプセル化した関数を渡す仕様。
    必要なときに get_ans, add, reset が呼ばれるので、そのタイミングで求解・情報の追加・初期化をおこなう。

    Usage:
        dot = DsuOnTree(n, root, ...)
        result = dot.execute()

    """

    def __init__(self, n, root, children, get_ans, add, reset):
        """
        Parameters
        ----------
        n : int
            頂点数
        root: int
            根の頂点番号
        children: list[list[Any]]
            s を根とした木の各 v の子のリスト。親は入っていない前提。
        get_ans : Callable[[int], None]
            頂点番号 u を引数とする。u の部分木の情報が揃ったときに呼ばれ、u についての答えを求める（呼び出し側で保存する）
        add : Callable[[int], None]
            頂点番号 u を引数とする。u の情報を加える処理を行う。
        reset : Callable[[int, list[int], list[int], list[int]], None]
            頂点番号 u と、オイラーツアーの結果を引数とする。u 以下の情報を除去し、データを初期化する処理を行う。
        """
        self.n = n
        self.root = root
        self.children = children
        self.get_ans = get_ans
        self.add = add
        self.reset = reset

        self.sizes = [0] * self.n
        self.make_subtree_sizes()

        self.is_heaviest_child = [False] * self.n
        sort_key = lambda v: self.sizes[v]
        for u in range(self.n):
            if self.sizes[u] > 1:
                children[u].sort(key=sort_key, reverse=True)
                self.is_heaviest_child[children[u][0]] = True

        self.tour = [0] * self.n
        self.first = [0] * self.n
        self.last = [0] * self.n
        self.euler_tour()

    def make_subtree_sizes(self):
        sizes = self.sizes
        children = self.children
        q = [~self.root, self.root]
        while q:
            u = q.pop()
            if u >= 0:
                for v in children[u]:
                    q.append(~v)
                    q.append(v)
                continue
            u = ~u
            res = 1
            for v in children[u]:
                res += sizes[v]
            sizes[u] = res

    def euler_tour(self):
        """ オイラーツアー
        木を何度も辿ることになるため、始めに1回のオイラーツアーで「v 以下の頂点」を配列範囲で走査できるようにしておく。（定数倍改善）

        以下を求めてインスタンスに登録する。
        self.tour[i] = 行きがけ順で i 番目にはじめて訪れる頂点番号
        self.first[v] = v がtourに現れるindex
        self.last[v] = v がtourを最後に通過したindex（tourは行きがけ順のみ記録するため実際には現れないが、親に帰る時点のindexの進捗）

        これらは内部的に使用するほか、 reset() に対象の頂点とともに渡される。
        以下で訪れられる v が、過不足なく u の部分木の頂点である。
        for vi in range(first[u], last[u]):
            v = tour[vi]
        """
        tour = self.tour
        first = self.first
        last = self.last
        idx = 0
        q = [~self.root, self.root]
        while q:
            u = q.pop()
            if u >= 0:
                tour[idx] = u
                first[u] = idx
                idx += 1
                for v in self.children[u]:
                    q.append(~v)
                    q.append(v)
            else:
                last[~u] = idx

    def add_all_subtree(self, u):
        tour = self.tour
        add = self.add
        for vi in range(self.first[u], self.last[u]):
            add(tour[vi])

    def execute(self):
        children = self.children
        get_ans = self.get_ans
        is_heaviest_child = self.is_heaviest_child

        q = [~self.root, self.root]

        while q:
            u = q.pop()
            if u >= 0:
                # 子は重さ降順にソート済みなので、順に追加するだけで、Heavy-child が最後に訪れられるようになる
                for v in children[u]:
                    q.append(~v)
                    q.append(v)
                continue
            u = ~u
            chu = children[u]
            self.add(u)
            for vi in range(1, len(chu)):
                self.add_all_subtree(chu[vi])
            get_ans(u)
            if is_heaviest_child[u] == False:
                self.reset(u, self.tour, self.first, self.last)


def solve(n, seed, m, f, qqq, ddd):
    parents, children, colors = decode_input(n, seed, m, f, qqq, ddd)
    # print(f'{parents=} {children=} {colors=}')

    color_count = [0] * n
    color_freq = [0] * (n + 1)
    color_freq[0] = n
    max_color_freq = 0
    ans = 0

    def get_ans(u):
        nonlocal ans
        u += 1
        ans += (max_color_freq ^ u) * (color_freq[max_color_freq] ^ u)
        ans %= 998244353

    def add(u):
        nonlocal max_color_freq
        c = colors[u]
        cc = color_count[c]
        color_count[c] += 1
        color_freq[cc] -= 1
        color_freq[cc + 1] += 1
        if max_color_freq <= cc:
            max_color_freq = cc + 1

    def reset(u, tour, first, last):
        nonlocal max_color_freq
        for vi in range(first[u], last[u]):
            v = tour[vi]
            c = colors[v]
            color_freq[color_count[c]] = 0
            color_count[c] = 0
        max_color_freq = 0

    dot = DsuOnTree(n, 0, children, get_ans, add, reset)
    dot.execute()

    return ans


n, seed, m, f = list(map(int, input().split()))
qqq = list(map(int, input().split()))
ddd = list(map(int, input().split()))
ans = solve(n, seed, m, f, qqq, ddd)
print(ans)