CodeQUEEN 2026 決勝 E,F,G,H問題メモ

from collections import deque
from itertools import accumulate


def solve(n, strings):
    coords = set()
    for l, r in strings:
        coords.add(l * 2)
        coords.add(r * 2 + 1)
    coords = sorted(coords)
    mapping = {c: i for i, c in enumerate(coords)}
    strings = [(mapping[l * 2], mapping[r * 2 + 1]) for l, r in strings]

    m = len(coords)
    acc = [0] * m
    for l, r in strings:
        acc[l] += 1
        acc[r] -= 1
    acc = list(accumulate(acc))

    links = [[] for _ in range(m)]
    for i in range(m - 1):
        if acc[i] == 0:
            links[i].append((0, i + 1))
        links[i + 1].append((0, i))
    for l, r in strings:
        links[l].append((1, r))

    q = deque()
    q.append((0, 0))
    costs = [1 << 60] * m
    costs[0] = 0
    while q:
        cu, u = q.popleft()
        if cu > costs[u]:
            continue
        for c, v in links[u]:
            if costs[v] <= cu + c:
                continue
            costs[v] = cu + c
            if c == 0:
                q.appendleft((cu + c, v))
            else:
                q.append((cu + c, v))

    ans = n - costs[-1]
    return ans


n = int(input())
strings = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, strings)
print(ans)

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


def solve(n, k, a, b, d):
    if k == 1:
        return n
    if a * b < k:
        return 0

    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)

    def ncr(n, r):
        return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD

    def nhr(n, r):
        return facts[n + r - 1] * finvs[r] % MOD * finvs[n - 1] % MOD

    # pre[i][j]: i 個（i<=d+1）の鍵盤を、左端と右端は必ず使って、j 個（j<=b）の鍵盤を押さえる方法の個数
    # pre2[j]: d+1 個の鍵盤中、j 個（j<b）を、左端は必ず使い、右端は使っても使わなくても良いとして押さえる方法の個数
    # pre3[i]: i 個（i<=N）の鍵盤中、b 個を、左端は必ず使い、右端は使っても使わなくても良いとして押さえる方法の個数
    pre = [[0] * (b + 1) for _ in range(d + 2)]
    pre2 = [0] * (b + 1)
    pre3 = [0] * (n + 1)
    pre[1][1] = 1
    pre2[1] = 1
    if b == 1:
        pre3[1] = 1
    for j in range(2, b + 1):
        for i in range(j, d + 2):
            pre[i][j] = ncr(i - 2, j - 2)
            if j < b:
                pre2[j] += pre[i][j]
                pre2[j] %= MOD
            else:
                pre3[i] = pre[i][j]
    for i in range(n):
        pre3[i + 1] += pre3[i]
        pre3[i + 1] %= MOD

    # dp[i][j][u]
    # i 個（i<=N）の鍵盤を、j 個（j<=K）押さえるうち、腕を u 本使っているような方法の個数。
    # ただし、左端は必ず押さえる。右端は
    # * j=K なら必ず押さえている。
    # * j<K なら、押さえていなくてもよい。直前の腕が b 本の指を使っていたらそれ以上の制約はないが、
    #   使っていなければ、直前に使った腕の左端とはD+2以上離れている。
    dp = [[[0] * (a + 1) for _ in range(k + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    for i in range(n):
        rem_keys = n - i
        for j in range(k):
            rem_push = k - j
            for u in range(a):
                # 残りを1腕で埋める
                if rem_push <= b:
                    for w in range(rem_push, d + 2):
                        if i + w > n:
                            break
                        dp[i + w][k][u + 1] += dp[i][j][u] * pre[w][rem_push]
                        dp[i + w][k][u + 1] %= MOD
                # 次の腕を b 本フルで使う
                if rem_push > b:
                    for w in range(b, rem_keys + 1):
                        dp[i + w][j + b][u + 1] += dp[i][j][u] * pre3[w]
                        dp[i + w][j + b][u + 1] %= MOD
                # 次の腕は b 本フルでは使わないが、d+1 個以上の鍵盤を消費する
                if n - i >= d + 1:
                    for w in range(d + 1, rem_keys + 1):
                        for v in range(1, min(b, rem_push)):
                            dp[i + w][j + v][u + 1] += dp[i][j][u] * pre2[v]
                            dp[i + w][j + v][u + 1] %= MOD

    ans = 0
    for i in range(1, n + 1):
        for u in range(1, a + 1):
            ans += (n + 1 - i) * dp[i][k][u]
            ans %= MOD
    return ans


n, k, a, b, d = list(map(int, input().split()))
ans = solve(n, k, a, b, d)
print(ans)

def solve(n, k, xxx):
    MOD = 998244353

    invs = [0] + [pow(i, -1, MOD) for i in range(1, 305)]

    def ncr(n, r):
        res = 1
        for i in range(r):
            res *= (n - i) * invs[i + 1] % MOD
            res %= MOD
        return res

    def sub(xxx):
        yyy = [(0, 0), (0, 1)] + [(i + 1, x - i) for i, x in enumerate(xxx)] + [(k + 1, xxx[-1] - k + 1)]
        dp = [-1]
        for j in range(1, len(yyy)):
            x2, y2 = yyy[j]
            res = 0
            for i in range(j):
                x1, y1 = yyy[i]
                res -= dp[i] * ncr(x2 - x1 + y2 - y1, x2 - x1)
            res %= MOD
            dp.append(res)
        return dp[-1]

    ans1 = sub(xxx)
    yyy = [n + 1 - x for x in reversed(xxx)]
    ans2 = ncr(n, k) - sub(yyy) + 1
    ans2 %= MOD
    return ans1, ans2


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

from heapq import heappush, heappop

from atcoder.dsu import DSU


def dijkstra(links: list[list[tuple[int, int]]], s: int, t: int = -1) -> int | list[int]:
    """ シンプルな Dijkstra
    :param links: links[u] = [ u から辺が伸びる先の (v, cost) のリスト ]
    :param s: 始点
    :param t: 終点
    :return: tが指定された場合はコスト、到達不可ならINF(1<<60)。指定されていない場合は距離配列
    """
    n = len(links)
    INF = 1 << 60
    dp = [INF] * n
    dp[s] = 0
    hq = [(0, s)]
    while hq:
        cost, u = heappop(hq)
        if dp[u] < cost:
            continue
        if u == t:
            return dp[u]
        for v, c in links[u]:
            new_cost = cost + c
            if dp[v] > new_cost:
                dp[v] = new_cost
                heappush(hq, (new_cost, v))
    if t == -1:
        return dp
    return INF


def solve(n, m, k, edges, animals):
    links = [[] for _ in range(n + n - 1)]
    edges2 = []
    for a, b, c, d in edges:
        a -= 1
        b -= 1
        links[a].append((b, d))
        links[b].append((a, d))
        edges2.append((c, a, b))
    for v, x in animals:
        v -= 1
        edges2.append((x, -1, v))
    edges2.sort(reverse=True)

    uft = DSU(n)
    extra_vertex = list(range(n))
    ei = n
    for c, a, b in edges2:
        if a == -1:
            i = extra_vertex[uft.leader(b)]
            links[b].append((i, 0))
        else:
            if uft.same(a, b):
                continue
            i = extra_vertex[uft.leader(a)]
            j = extra_vertex[uft.leader(b)]
            links[ei].append((i, 0))
            links[ei].append((j, 0))
            ni = uft.merge(a, b)
            extra_vertex[ni] = ei
            ei += 1

    ans = dijkstra(links, 0, n - 1)
    return ans


n, m, k = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(m)]
animals = [list(map(int, input().split())) for _ in range(k)]
ans = solve(n, m, k, edges, animals)
print(ans)