ユニークビジョンプログラミングコンテスト2024 クリスマス（AtCoder Beginner Contest 385）E,F,G問題メモ

def solve(n, edges):
    degrees = [0] * n
    links = [[] for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        degrees[u] += 1
        degrees[v] += 1
        links[u].append(v)
        links[v].append(u)

    vertices = 0
    for u in range(n):
        vd = [degrees[i] for i in links[u]]
        vd.sort(reverse=True)
        for i, d in enumerate(vd, start=1):
            vertices = max(vertices, 1 + i * d)
    return n - vertices


n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
ans = solve(n, edges)
print(ans)

特に新たな価値は無いので読まなくて良い。

$i=2,3,...,N$ につき、以下を調べる。

• $1～i$ の中から取れる2点の中で、$i$ を通る直線が切片最大となることはあるか？ ある場合、その切片は？

以下の情報を残すようにすると、求められる。

• $1～i-1$ の中から取れる2点の中での「最大切片 $B$」と「その時の直線の傾き $S$」
• $1～i-1$ の各頂点を通る傾き $S$ の直線の中で、切片最大を与える点の座標 $X_m,H_m$
  • そのような点が複数ある場合、最も $X$ 座標が大きいもの

$(X_m,H_m),(X_i,H_i)$ を通る直線の切片が $B$ を更新するなら $B,S,X_m,H_m$ を更新する。
更新しないなら、$(X_i,H_i)$ を通る傾き $S$ の直線の切片が $B$ 以上なら $X_m,H_m$ を更新する。
そうでなければ何もしない。

……でもこれ、絶対に上2つのどっちかに当てはまるので、 結果的に毎回 $(X_{i-1},H_{i-1}),(X_i,H_i)$ を調べていることになり、解法1と同じことになる。

from fractions import Fraction


def solve(n, buildings):
    ans = Fraction(-(1 << 60))
    slope = Fraction(1 << 60)
    bx, by = buildings[0]
    for i in range(1, n):
        x, y = buildings[i]
        tmp = Fraction(y - by, x - bx)
        sec = y - tmp * x
        if ans <= sec:
            bx, by = x, y
            ans = sec
            slope = tmp
            continue
        sec = y - slope * x
        if ans <= sec:
            bx, by = x, y
    return ans


n = int(input())
buildings = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, buildings)
if ans < 0:
    print(-1)
else:
    print(ans.numerator / ans.denominator)

import os
import sys
from collections import deque

import numpy as np

MOD = 998244353
SUM_E = np.array(
    [911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456,
     131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443,
     56250497, 867605899, 0, 0, 0, 0, 0, 0, 0, 0], np.int64)
SUM_IE = np.array(
    [86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882,
     927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183,
     824071951, 103369235, 0, 0, 0, 0, 0, 0, 0, 0], np.int64)


def convolution(aaa, bbb):
    def bit_length(n):
        x = 0
        while 1 << x < n:
            x += 1
        return x

    def bit_scan_forward(n):
        x = 0
        while n & 1 == 0:
            n >>= 1
            x += 1
        return x

    def mod_pow(x, a, MOD):
        ret = 1
        cur = x
        while a > 0:
            if a & 1:
                ret = ret * cur % MOD
            cur = cur * cur % MOD
            a >>= 1
        return ret

    def butterfly(aaa, mod, sum_e):
        n = aaa.size
        h = bit_length(n)

        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p] * now % mod
                    aaa[i + offset] = (l + r) % mod
                    aaa[i + offset + p] = (l - r) % mod
                now = now * sum_e[bit_scan_forward(~s)] % mod

    def butterfly_inv(aaa, mod, sum_ie):
        n = aaa.size
        h = bit_length(n)

        for ph in range(h, 0, -1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p]
                    aaa[i + offset] = (l + r) % mod
                    aaa[i + offset + p] = ((l - r) * inow) % mod
                inow = inow * sum_ie[bit_scan_forward(~s)] % mod

    n = aaa.size
    m = bbb.size
    k = n + m - 1
    z = 1 << bit_length(k)
    raaa = np.zeros(z, np.int64)
    rbbb = np.zeros(z, np.int64)
    raaa[:n] = aaa
    rbbb[:m] = bbb
    butterfly(raaa, MOD, SUM_E)
    butterfly(rbbb, MOD, SUM_E)
    for i in range(z):
        raaa[i] = raaa[i] * rbbb[i] % MOD
    butterfly_inv(raaa, MOD, SUM_IE)
    iz = mod_pow(z, MOD - 2, MOD)
    for i in range(k):
        raaa[i] = raaa[i] * iz % MOD
    return raaa[:k]


SIGNATURE = '(i8[:],i8[:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('convolution', SIGNATURE)(convolution)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import convolution
else:
    from numba import njit

    convolution = njit(SIGNATURE, cache=True)(convolution)
    print('compiled', file=sys.stderr)


def solve(n, k):
    if n == 1:
        if k == 0:
            return 1
        else:
            return 0
    q = deque()
    for i in range(n - 1):
        q.append(np.array([1, i, 1], dtype=np.int64))
    while len(q) > 1:
        f = q.popleft()
        g = q.popleft()
        h = convolution(f, g)
        q.append(h)
    f = q[0]
    ans = f[k + n - 1]
    return ans


n, k = map(int, input().split())
ans = solve(n, k)
print(ans)