AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）E,F,G問題メモ

AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）

E - Fruit Lineup

問題文

$A$ 個のリンゴと $B$ 個のオレンジと $C$ 個のバナナと $D$ 個のブドウがあります。
これらの $A+B+C+D$ 個の果物を、以下の条件全てを満たすように左右一列に並べる方法は何通りありますか？
- リンゴはすべて、バナナよりも左側に並べる。
- リンゴはすべて、ブドウよりも左側に並べる。
- オレンジはすべて、ブドウよりも左側に並べる。
ただし、同じ種類の果物同士は区別できないとします。
答えを $998244353$ で割った余りを求めてください。

制約

$1 \leq A \leq 10^6$
$1 \leq B \leq 10^6$
$1 \leq C \leq 10^6$
$1 \leq D \leq 10^6$
$A, B, C, D$ は全て整数

解法

まず、$A$ 個のリンゴと $D$ 個のブドウをこの順に並べる。

 リ リ リ リ リ リ ブ ブ ブ ブ ブ ブ

$B$ 個のオレンジはここに挿入できて、

 リ リ リ リ リ リ ブ ブ ブ ブ ブ ブ
^  ^  ^  ^  ^  ^  ^

$C$ 個のバナナはここに挿入できる。リとブの間に挿入したオの数により、バの挿入箇所の数が異なる。

 リ リ リ リ リ リ オ オ ブ ブ ブ ブ ブ ブ
                  ^  ^  ^  ^  ^  ^  ^  ^  ^

よって、リとブの間に挿入するオの数を $i=0～B$ に固定した場合の数をそれぞれ求めればよい。

$\displaystyle \sum_{i=0}^{B} {}_{A}H_{B-i} \times {}_{D+i+1}H_{C}$

Python3

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(a, b, c, d):
    MOD = 998244353
    facts, finvs = precompute_factorials(a + b + c + d + 1, MOD)

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

    ans = 0
    for i in range(b + 1):
        ans += nhr(a, b - i) * nhr(d + 1 + i, c)
        ans %= MOD
    return ans


a, b, c, d = map(int, input().split())
ans = solve(a, b, c, d)
print(ans)

F - Chord Crossing

問題文

円周上に $2N$ 個の点が等間隔に並んでおり、ある点から始めて時計回りに $1,2,\dots,2N$ の番号が付けられています。
これらの点を結ぶ $M$ 本の線分 $1,2,\dots,M$ が存在し、線分 $i$ は点 $A_i$ と点 $B_i$ を結んでいます。
- ここで、$A_i$ と $B_i$ は相異なる偶数です。
- また、これらの線分のうちのどの $2$ つの線分も共有点を持たないことが保証されます。
$Q$ 個のクエリを処理してください。$j$ 番目のクエリは以下の通りです。
- 相異なる $2$ つの奇数 $C_j, D_j$ が与えられる。
- 上で与えられた $M$ 本の線分 $1,2,\dots,M$ のうち、点 $C_j$ と点 $D_j$ を結ぶ線分と共有点を持つものの本数を求めよ。

制約

$2\leq N \leq 10^6$
$1\leq M \leq \min\left(\lfloor\frac{N}{2}\rfloor, 2\times 10^5\right)$
$1\leq Q \leq 2\times 10^5$
$1\leq A_i\lt B_i\leq 2N$
$1\leq C_j\lt D_j\leq 2N$
$A_i, B_i$ は偶数
$C_j, D_j$ は奇数
どの $i_1, i_2\ (i_1 \neq i_2)$ についても、線分 $i_1$ と線分 $i_2$ は共有点を持たない
入力は全て整数

解法

$1$ と $2N$ で輪をぶった切り、直線に開く。線分とクエリを区間で表現する。

       1 2 3 4 5 6 7 8
線分     |---|   |---|
クエリ |---|            → 1
       |-------|        → 0
           |-------|    → 2

クエリの答えは、クエリ区間に「左端と右端の内いずれか一方だけを含む」線分区間の個数となる。

片方ずつ別々に求める。まずは、各線分区間に対し「左端を含み右端は含まない」クエリ区間の個数を求める。

これは、長さ $2N$ のセグメント木 $S$ を用意し、イベントソートのように $i=1,...,2N$ の順に以下を処理すれば可能となる。

$i$ を左端とする線分区間に対し、$S[i]$ に1加算する
$i$ を右端とする線分区間に対し、その左端を $j$ とし、$S[j]$ から1引く
$i$ を右端とするクエリ区間に対し、$S$ 上の $C_i～D_i$ の和を答えとして加算する

同様のことを逆順にやると、「右端を含み左端は含まない」クエリ区間も求められる。

Python3

from collections import defaultdict
from operator import add


class SegmentTreeInjectable:
    """
    単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木

    [生成]
    SegmentTreeInjectable(n, identity_factory, func)
    SegmentTreeInjectable.from_array(array, identity_factory, func)  # 既存の配列より作成

    [関数]
    add(i, x)               Aiにxを加算
    update(i, x)            Aiをxに書き換え
    get_range(a, b)         [a, b) の集約値を得る
    get_all()               全ての集約値を得る
    get_point(i)            Aiを得る
    leftmost(a, b, x, ev)   [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
    rightmost(a, b, x, ev)  [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
    debug_print()           深さ毎に整形して出力する
    """

    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory

    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins

    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)

    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)

    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            i >>= 1
            lch = i << 1
            rch = lch | 1
            tree[i] = func(tree[lch], tree[rch])

    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return func(result_l, result_r)

    def get_all(self):
        return self.tree[1]

    def get_point(self, i):
        return self.tree[i + self.offset]

    def leftmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        r_found = -1
        while l < r:
            if l & 1:
                if ev(x, tree[l]):
                    return self._leftmost_sub(l, x, ev)
                l += 1
            if r & 1:
                if ev(x, tree[r - 1]):
                    r_found = r - 1
            l >>= 1
            r >>= 1

        if r_found == -1:
            return -1

        return self._leftmost_sub(r_found, x, ev)

    def _leftmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l]):
                i = l
            else:
                i = l + 1
        return i - self.offset

    def rightmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        l_found = -1
        while l < r:
            if r & 1:
                if ev(x, tree[r - 1]):
                    return self._rightmost_sub(r - 1, x, ev)
            if l & 1:
                if ev(x, tree[l]):
                    l_found = l
                l += 1
            l >>= 1
            r >>= 1

        if l_found == -1:
            return -1

        return self._rightmost_sub(l_found, x, ev)

    def _rightmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l + 1]):
                i = l + 1
            else:
                i = l
        return i - self.offset

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1


def solve(n, m, lines, q, queries):
    line_fwd_events = {}
    line_bwd_events = {}
    for a, b in lines:
        line_fwd_events[a] = -1
        line_fwd_events[b] = a
        line_bwd_events[a] = b
        line_bwd_events[b] = -1
    query_fwd_events = defaultdict(list)
    query_bwd_events = defaultdict(list)
    for i, (c, d) in enumerate(queries):
        query_fwd_events[d].append((i, c))
        query_bwd_events[c].append((i, d))

    ans = [0] * q
    sgt = SegmentTreeInjectable(n * 2 + 1, int, add)
    for i in range(1, n * 2 + 1):
        if i % 2 == 1:
            if i not in query_fwd_events:
                continue
            for qi, c in query_fwd_events[i]:
                ans[qi] += sgt.get_range(c, i)
        else:
            if i not in line_fwd_events:
                continue
            a = line_fwd_events[i]
            if a == -1:
                sgt.add(i, 1)
            else:
                sgt.add(a, -1)

    sgt = SegmentTreeInjectable(n * 2 + 1, int, add)
    for i in range(n * 2, 0, -1):
        if i % 2 == 1:
            if i not in query_bwd_events:
                continue
            for qi, d in query_bwd_events[i]:
                ans[qi] += sgt.get_range(i, d)
        else:
            if i not in line_bwd_events:
                continue
            b = line_bwd_events[i]
            if b == -1:
                sgt.add(i, 1)
            else:
                sgt.add(b, -1)

    return ans


n, m = map(int, input().split())
lines = [tuple(map(int, input().split())) for _ in range(m)]
q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, m, lines, q, queries)
print('\n'.join(map(str, ans)))

G - Range Shuffle Query

問題文

長さ $N$ の数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。
$Q$ 個のクエリが与えられるので処理してください。
クエリでは整数 $L, R, X$ が与えられるので次の問題を解いてください。
- $A$ の $L$ 番目から $R$ 番目までの要素を取り出してできる数列 $B=(A_L, A_{L+1}, \dots, A_R)$ があります。
- あなたは以下の一連の操作をちょうど $1$ 回行います。
  - まず、$B$ から値が $X$ 以上の要素を全て取り除く。
  - 次に、$B$ の要素を自由に並べ替える。
- 操作後の $B$ としてあり得るものは何通りありますか？答えを $998244353$ で割った余りを求めてください。

制約

$1 \leq N \leq 2.5 \times 10^5$
$1 \leq Q \leq 2.5 \times 10^5$
$1 \leq A_i \leq N$
$1 \leq L \leq R \leq N$
$1 \leq X \leq N$
入力される値は全て整数

解法

クエリの答えは以下となる。クエリ $[L,R]$ 間にある値 $a$ の個数を $C_a$ とする。

$\displaystyle (クエリ区間内にあるX未満の値の個数)! \times \prod_{a=1}^{X-1}\frac{1}{C_a!}$

よって、各クエリ区間 $[L,R]$ における

$X$ 未満の値の個数
$X$ 未満の値の $\dfrac{1}{C_a!}$ の総積

がわかればよいということになる。これは、例えば以下のデータ構造やテクニックで管理できる。

Fenwick Tree, Segment Tree
- $A_i$ を添字に持ち、個数の区間SUMと、階乗の逆数の区間PRODを2本で管理
平方分割
- 同様に $A_i$ を添字に持ち、個数の区間SUMと、階乗の逆数の区間PRODを管理

Mo's Algorithm で、区間を伸び縮みさせ $A_i$ が入ったり出たりしたときに、これらのデータ構造の状態を適切に更新できればよい。

Mo's algorithm - アルゴリズムとデータ構造大全

ここで、一般的には FenwickTree と平方分割では前者で実装する方が速そうだが。。。

今回の場合、前者ではTLE、後者が想定解法となる。なんてこった。

Mo's Algorithm では、以下の2つの処理が必要となる。

(A) 区間を伸び縮みさせたとき、状態を更新する処理
(B) 伸び縮み後、答えを集計する処理

Mo's Algorithm で回数が多いのは (A) の方である。
そしてこの問題の場合、

FenwickTree,SegmentTree:
- (A) の計算量は $O(\log{N})$、(B) の計算量は $O(\log{N})$
平方分割:
- (A) の計算量は $O(1)$、(B) の計算量は $O(\sqrt{N})$

回数の多い処理(A)において平方分割の方が優れた計算量となる。

全体の計算量は、Mo's のバケットサイズを $\frac{N}{\sqrt{Q}}$、平方分割のバケットサイズを $\sqrt{N}$ とすることで、$O(N \sqrt{Q} + Q \sqrt{N})$ となる。第1項が(A)、第2項が(B)の計算量となる。ちなみに、FenwickTree解法では $O(N\sqrt{Q}\log{N} + Q \log{N})$ で、バランスが悪くなっていることが分かる。

AtCoderでは遅い言語でもACできるよう、想定解法にlog1個つけてもACできるくらい余裕のある実行時間制限の問題が多いように思うが、今回はlogを落とすことが要点となった。

Python3

import os
import sys

import numpy as np


def solve(inp):
    MOD = 998244353

    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 prepare_factorials(n, MOD):
        factorials = np.ones(n + 1, np.int64)
        for m in range(1, n + 1):
            factorials[m] = factorials[m - 1] * m % MOD
        inversions = np.ones(n + 1, np.int64)
        inversions[n] = mod_pow(factorials[n], MOD - 2, MOD)
        for m in range(n, 1, -1):
            inversions[m - 1] = inversions[m] * m % MOD
        return factorials, inversions

    n, q = inp[:2]
    aaa = inp[2:n + 2]
    lll = inp[n + 2::3] - 1
    rrr = inp[n + 3::3]
    xxx = inp[n + 4::3]

    facts, finvs = prepare_factorials(n, MOD)

    max_n = 1 << 18

    def hilbert_order(x, y):
        d = 0
        s = max_n >> 1
        while s > 0:
            rx = (x & s) > 0
            ry = (y & s) > 0
            d += s * s * ((rx * 3) ^ ry)
            s >>= 1
            if ry > 0:
                continue
            if rx > 0:
                x = max_n - 1 - x
                y = max_n - 1 - y
            x, y = y, x
        return d

    buckets = []
    for qi in range(q):
        l = lll[qi]
        r = rrr[qi]
        x = xxx[qi]
        d = hilbert_order(l, r)
        buckets.append((d, qi, l, r, x))
    buckets.sort()

    bucket_size = 500
    bucket_count = n // bucket_size + 1
    count_raw = np.zeros(n + 1, np.int64)
    count_bucket = np.zeros(bucket_count, np.int64)
    prod_raw = np.ones(n + 1, np.int64)
    prod_bucket = np.ones(bucket_count, np.int64)

    def update_bucket(a, d):
        pc = count_raw[a]
        b = a // bucket_size
        count_raw[a] += d
        count_bucket[b] += d
        prod_raw[a] = finvs[pc + d]
        prod_bucket[b] *= facts[pc] * finvs[pc + d] % MOD
        prod_bucket[b] %= MOD

    def get_ans(x):
        b = (x - 1) // bucket_size
        cnt = count_bucket[:b].sum()
        cnt += count_raw[b * bucket_size:x].sum()
        prd = 1
        for i in range(b):
            prd *= prod_bucket[i]
            prd %= MOD
        for i in range(b * bucket_size, x):
            prd *= prod_raw[i]
            prd %= MOD
        result = facts[cnt] * prd % MOD
        return result

    l = 0
    r = 0
    ans = np.zeros(q, np.int64)

    for _, qi, tl, tr, x in buckets:
        while r < tr:
            a = aaa[r]
            update_bucket(a, 1)
            r += 1
        while r > tr:
            r -= 1
            a = aaa[r]
            update_bucket(a, -1)
        while l < tl:
            a = aaa[l]
            update_bucket(a, -1)
            l += 1
        while l > tl:
            l -= 1
            a = aaa[l]
            update_bucket(a, 1)

        ans[qi] = get_ans(x)

    return ans


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

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

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

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

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

目次

AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）E,F,G問題メモ

E - Fruit Lineup

問題文

制約

解法

F - Chord Crossing

問題文

制約

解法

G - Range Shuffle Query

問題文

制約

解法