AtCoder ABC217 個人的メモ

A - Lexicographic Order

S, T = input().split()

if S < T:
    print("Yes")
else:
    print("No")

B - AtCoder Quiz

4つのコンテストと開催されているコンテストのxorをとればおｋ

S = {input() for _ in range(3)}

res = {"ABC", "ARC", "AGC", "AHC"}

print((res ^ S).pop())

C - Inverse of Permutation

N = int(input())
P = list(map(int, input().split()))

ans = [0] * N
for i, p in enumerate(P):
    ans[p - 1] = i + 1

print(*ans)

D - Cutting Woods

$Q\leq 2\times 10^5$なので各クエリを$O(10)$ぐらいで処理したい。
$c_i=2$のときは線$x_i$を含む木材の両端の$x$が分かれば木材の長さは$(左端のx)-(右端のx)$で$O(1)$で求まる。
これは$(左端のx)$は$(x_i以下での最大の切断済みのx)$、$(右端のx)$は$(x_i以上で最小の切断済みのx)$と言い換えることができる。
この2つはそれぞれ区間最小値と区間最大値なので、セグメント木を使えば配列の長さを$N$としたときに値の更新と参照が$O(\log N)$でできる。
今回の問題では木材の長さは$0\leq L\leq 10^9$となり、セグ木の配列の長さを$L$とするとACできなさそう。
ここで$Q\leq 2\times 10^5$なので、$x_i$の種類数は$2\times 10^5$以下と分かる。
つまり$x_i$を座標圧縮すればセグ木の配列の長さも$2\times 10^5$でおｋ。
$c_i=2$のときはこれで良さそう。
$c_i=1$のときもセグ木の更新は$O(\log N)$で済む。
よって、全体で$O(Q\log Q)$となり十分に高速となる。

セグ木の実装部分

class segtree:
    """
    Segment tree\\
    Store value as object type and optional function for binary operarion.\\
    "get" function return a value by binary operarion result. O(logN)\\
    "update" function update tree's a value. O(logN)

    Attributes
    ----------
    n : int
        Number of elements
    identity element_func : func
        Identity_element for initialization.\\
        If operator is * and identiry element is e, e * A = A and A * e = A.
    binary_operation_func : func
        Function for binary operation x and y.\\
        Function must have associative law.\\
        If operator is *, (A * B) * C = A * (B * C).

    Methods
    -------
    update(i, x)
        Update tree[i] value to x
    get(a, b)
        Get value from [a, b).\\
        Include a but not include b, return a merged value.
    """

    def __init__(self, n: int, identity_element_func, binary_operation_func):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of elements
        identity_element_func : func
            Identity element for initialization\\
            If operator is * and identiry element is e, e * A = A and A * e = A
        binary_operation_func : func
            Function for binary operation x and y.\\
            Function must have associative law.\\
            If operator is *, (A * B) * C = A * (B * C)
        """
        self.identity = identity_element_func
        self.binary = binary_operation_func
        self.offset = 1 << (n - 1).bit_length()  # offsetはnより大きい2の冪数
        self.tree = [self.identity() for _ in range(self.offset << 1)]

    @classmethod
    def from_array(cls, arr, identity_element_func, binary_operation_func):
        """Initialize from array"""
        ins = cls(len(arr), identity_element_func, binary_operation_func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            lch = i << 1
            ins.tree[i] = binary_operation_func(
                ins.tree[lch], ins.tree[lch + 1])
        return ins

    def update(self, index: int, x: int):
        """
        Overwrite segment-tree's a value and update parent nodes.
        This method updates the value to the new value regardless of the previous value.

        Parameters
        ----------
        index : int
            index of update value
        x     : int
            new value
        """
        index += self.offset
        self.tree[index] = x
        while index > 1:
            index >>= 1  # 右ビットシフトで親ノードのインデックスへ移動
            lch = index << 1
            self.tree[index] = self.binary(self.tree[lch], self.tree[lch + 1])

    def get(self, left: int, right: int) -> int:
        """
        Get a specific value by result of binary operation from interval [left, right).

        Parameters
        ----------
        left, right : int
            Index of interval.\\
            This is hald open interval, this interval include left but not right.
        """
        result_l = self.identity()
        result_r = self.identity()
        left += self.offset
        right += self.offset
        while left < right:
            if left & 1:
                result_l = self.binary(result_l, self.tree[left])
                left += 1
            if right & 1:
                right -= 1
                result_r = self.binary(self.tree[right], result_r)
            left >>= 1
            right >>= 1

        return self.binary(result_l, result_r)

L, Q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(Q)]
INF = 10 ** 18

# 座標圧縮
X = set()
x_to_i = {}
for c, x in query:
    X.add(x)
X = sorted(X)
for i, x in enumerate(X):
    x_to_i[x] = i

# 線xiを含む木材の右端のxを返すセグ木
search_right_end = segtree(len(X), lambda: INF, min)
search_right_end.update(len(X) - 1, L)
# 線xiを含む木材の左端のxを返すセグ木
search_left_head = segtree(len(X), lambda: 0, max)
search_left_head.update(0, 0)
for c, x in query:
    i = x_to_i[x]
    if c == 1:
        search_right_end.update(i, x)
        search_left_head.update(i, x)
    else:
        right = search_right_end.get(i, len(X))
        left = search_left_head.get(0, i)
        print(right - left)

E - Sorting Queries

from heapq import heappop, heappush
from collections import deque

Q = int(input())
# Aはソートされたxであるpriority_queueとまだソートされていないxであるAの順に並んでいる
A = deque([])
priority_queue = []
for _ in range(Q):
    c, *x = map(int, input().split())
    if c == 1:
        A.append(x[0])
    if c == 2:
        if priority_queue:
            print(heappop(priority_queue))
        else:
            print(A.popleft())
    if c == 3:
        while A:
            heappush(priority_queue, A.popleft())

F - Make Pair

区間dp

N, M = map(int, input().split())
N2 = N * 2
terms = [[] for _ in range(N2)]
for _ in range(M):
    a, b = map(lambda a: int(a) - 1, input().split())
    terms[a].append(b)
MOD = 998244353

# 組み合わせの数を事前に計算しておく(今のatcodeeのpypyでmath.combが使えない)
fac = [1]
for i in range(1, N + 1):
    fac.append(fac[-1] * i % MOD)

comb = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    for j in range(N + 1):
        comb[i][j] = fac[i] * pow(fac[j] * fac[i - j], MOD - 2, MOD)

# dp[i][j]:=[i,j)の範囲の生徒のみで作るペアの場合の数
dp = [[0] * (N2 + 1) for _ in range(N2 + 2)]
for i in range(N2 + 1):
    dp[i][i] = 1
# (left,mid)のペア
for left in range(N2 - 1, -1, -1):
    for right in range(left, N2 + 1, 2):
        num_pairs = (right - left) // 2
        for mid in terms[left]:
            res = comb[num_pairs][(right - (mid + 1)) // 2]
            dp[left][right] += dp[left + 1][mid] * dp[mid + 1][right] * res
            dp[left][right] %= MOD

print(dp[0][-1])