AtCoder Beginner Contest 449 E,F,G問題メモ

AtCoder Beginner Contest 449

D,E,Fあたりは実装が重めで時間との勝負になった。

E - A += v

• 整数 $N,M$ と各要素が $1$ 以上 $M$ 以下である長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
• この整数列 $A$ に対して以下の操作を $10^{100}$ 回行います。
  • $1$ 以上 $M$ 以下の整数のうち $A$ における出現回数が最も少ないものを $v$ とする。
    • ただし、そのような $v$ が複数存在する場合はその中で値が最小のものとする。
  • $A$ の末尾に $v$ を追加する。

• $Q$ 個のクエリが与えられます。 $i$ 番目のクエリでは整数 $X_i$ が与えられます。
• 各クエリに対し、操作を $10^{100}$ 回行った後の $A_{X_i}$ の値を求めてください。

• $1\le N,M\le 5\times 10^5$
• $1\le A_i \le M$
• $1\le Q\le 2\times 10^5$
• $1\le X_i \le 10^{18}$
• 入力される値は全て整数

$1～M$ の出現回数のヒストグラムを作ると、末尾に追加される要素は、下から順に、同じ段では左から順になる。
最も高い所まで埋まった後（下図⑬～）は、単純に $1～M$ が繰り返されることになる。

M = 5
A = (5, 1, 1, 3, 5, 5, 2, 5)

⑬⑭⑮⑯⑰    ■: 初期状態の出現回数のヒストグラム
⑨⑩⑪⑫■    ①: 追加順
⑤⑥⑦⑧■        ※①はAにおいては第 N+1 項に当たる点に注意
■②③④■
■■■①■
----------
１２３４５

下から段毎に処理する。以下を定義する。

• $S:=t$ 段目の処理の時点で、出現回数が $t$ 回未満の要素のソート済み集合
  • 上例では、1段目で $4$、2段目で $2,3$、3段目で $1$、、、が追加されていく
• $K:=t$ 段目の処理開始時点で、次に追加される要素が $A$ において第何項にあたるか。$K=N+1$ で初期化

$S$ は、SortedSet や、FenwickTree上の二分探索などで実装できる。

また、クエリは先読みした上で小さい順にソートしておく。どこまで処理したかのポインタを $q$ とする。

初期の $A$ の値をそのまま参照すればよい。

$t=1,2,...$ の各段で、

• 出現回数が $t-1$ 回だった要素を全て $S$ に追加する。
• $K \le X_q \lt K+|S|$ なら、そのクエリへの答えを $S[X_q-K]$ とし、$q$ を1増やす。
• $K$ に $|S|$ を加算する。

$|S|=M$ になったら終了

$j=(X_q-K) \mod{M}$ として、$j+1$ が答えである。

$X_q$ の上限はでかいので、最後まで②の方法でやるとTLEする。

Python3

from collections import Counter
from operator import itemgetter

from sortedcontainers import SortedSet


def solve(n, m, aaa, q, queries):
    queries = sorted(enumerate(queries), key=itemgetter(1))
    ss = SortedSet()
    ans = [0] * q
    cnt = Counter(aaa)
    appeared_count = {i: [] for i in range(n + 1)}
    for a in range(1, m + 1):
        appeared_count[cnt[a]].append(a)

    t = 0
    while t < q and queries[t][1] <= n:
        qi, x = queries[t]
        ans[qi] = aaa[x - 1]
        t += 1

    k = n
    for i in range(n):
        for a in appeared_count[i]:
            ss.add(a)
        if len(ss) == n:
            break
        while t < q and queries[t][1] <= k + len(ss):
            qi, x = queries[t]
            ans[qi] = ss[x - k - 1]
            t += 1
        k += len(ss)

    while t < q:
        qi, x = queries[t]
        ans[qi] = (x - k - 1) % m + 1
        t += 1

    return ans


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

F - Grid Clipping

• $H$ 行 $W$ 列のグリッドがあります。
• $N$ 個のマス $(R_k,C_k)$（$k=1,2,...,N$）は黒で、それ以外の $HW-N$ マスは白で塗られています。
• このグリッドの中の縦 $h$ 行、横 $w$ 列の長方形領域であって、含まれるマスが全て白で塗られているようなものがいくつあるか求めてください。

• $1\le h\le H\le 10^9$
• $1\le w\le W\le 10^9$
• $0\le N\le 2\times 10^5$
• $1\le R_k\le H$
• $1\le C_k\le W$
• $(R_{k_1},C_{k_1}) \neq (R_{k_2},C_{k_2})$ $(k_1 \neq k_2)$
• 入力される値は全て整数

平面走査。

「長方形として取ったときの最も左上のマスの座標」で長方形を表すことにする。
座標を 0-indexed（グリッドの左上を $(0,0)$）とすると、長方形の座標 $(i,j)$ は $0 \le i \le H-h$、$0 \le j \le W-w$ の範囲を取れる。

黒マス1個に対し、「もし他の黒マスが無かったとして、その黒マスのために全て白ではなくなってしまう長方形」が、 最大 $hw$ 個できる。そのような長方形の左上マスは、矩形状に分布する。

h=3 w=2
□□□□□□□□      □□□□□□－－
□□□□□□□□      □□×××□－－  ×のマスを左上とする長方形が
□□□□■□□□  →  □□×××□－－  "全て白"では無くなってしまう。
□□□□□□□□      －－－－－－－－  （－は長方形の左上にならないマス）

□■□□□□□□      ××□□□□－－
□□□□□□□□      □□□□□□－－  端の方は、グリッドをはみ出したり
□□□□□□□□  →  □□□□××－－  －に被ったりしない範囲が×になる。
□□□□□□■□      －－－－－－－－

黒マス $(R,C)$ に対し、そのマスを右下とした矩形範囲、 具体的には縦 $[max(0,R-h+1),min(H-h+1,R+1))$、横 $[max(0,C-w+1),min(W-w+1,C+1))$ の矩形が“×”になる。

問題は、「$(H-h+1) \times (W-w+1)$ のグリッドを、$N$ 個の矩形で黒に塗る。塗られていないマスは何マス残る？」という問題に言い換えられる。

これを求めたいが、黒マス同士が近いと矩形が何個も重なり合う可能性があるので、単純にはいかない。

各マスが「いくつの矩形で塗られているか」をグリッドで表せば、答えはその中の $0$ の個数である。

□□□□□□□□      ０１１１００－－    各マスが
□□□■□□□□      １２３２１０－－    いくつの矩形で塗られているか
□□■□■□□□  →  １１２１１０－－   （－ は長方形の左上になれないマス）
□□□□□□□□      －－－－－－－－    → 答えは０の個数

しかし実際に $O(HW)$ のサイズのグリッドを構築するわけにはいかないので、「行」単位で考え、差分更新していく。
行を $r=0,1,...,H-h$ の順に上から処理することにすると、

• その行で新しく始まる各矩形に対し、その矩形が配置される区間のカウンタを1ずつ増やす
  • $r=max(0,R_k-h+1)$ を満たす $k$ に対し、$[max(0,C-w+1),min(W-w+1,C+1))$ の範囲に1加算する
• その行で終わる各矩形に対し、その矩形が配置されていた区間のカウンタを1ずつ減らす
  • $r=min(H-h+1,R+1)$ を満たす $k$ に対し、$[max(0,C-w+1),min(W-w+1,C+1))$ の範囲から1減算する
• その行の $0$ の個数をカウントし、答えに加算する

と、適切にこれを更新できる。

これは区間加算・区間集約なので遅延評価セグメント木で可能なのだが、持たせる情報が少し難しい。 以下の情報を持たせると上手くいく。

• (区間内最小値, 区間内最小値の個数)

「$0$ の個数」を直接持たせてしまうと、ある矩形が終了して $1→0$ のマスができた時、新しく何個の $0$ ができるのかわからない。「最小値の個数」として持たせておくことで、これが特定できるようになる。

また $H,W$ が非常に大きいため、このままでは TLE となってしまう。
座標圧縮をおこなうと、縦・横ともに区間数を $O(N)$ にでき、全体 $O(N \log{N})$ となる。

Python3

from collections import defaultdict
from operator import add

from atcoder.lazysegtree import LazySegTree


def solve(h, w, qh, qw, n, blacks):
    ccc = {0, w - qw + 1}
    for r, c in blacks:
        c -= 1
        ccc.add(max(0, c - qw + 1))
        ccc.add(min(w - qw + 1, c + 1))
    ccc = sorted(ccc)
    mapping_c = {c: i for i, c in enumerate(ccc)}
    # print(f'{ccc=}')

    events = defaultdict(list)
    for r, c in blacks:
        r -= 1
        c -= 1
        ur = max(0, r - qh + 1)
        dr = min(h - qh + 1, r + 1)
        lc = mapping_c[max(0, c - qw + 1)]
        rc = mapping_c[min(w - qw + 1, c + 1)]
        events[ur].append((lc, rc, 1))
        events[dr].append((lc, rc, -1))
    if h - qh + 1 not in events:
        events[h - qh + 1] = []
    # print(events)

    # (区間幅, 最小値, 最小値の個数)
    def merge(a, b):
        if a[1] == b[1]:
            return [a[0] + b[0], a[1], a[2] + b[2]]
        elif a[1] < b[1]:
            return [a[0] + b[0], a[1], a[2]]
        else:
            return [a[0] + b[0], b[1], b[2]]

    def mapping(a, b):
        if a == 0:
            return b
        return [b[0], b[1] + a, b[2]]

    init = []
    for i in range(len(ccc) - 1):
        bw = ccc[i + 1] - ccc[i]
        init.append((bw, 0, bw))

    lst = LazySegTree(merge, [0, 1 << 60, 0], mapping, add, 0, init)

    def get_zero():
        ap = lst.all_prod()
        if ap[1] == 0:
            return ap[2]
        else:
            return 0

    ans = 0
    pr = 0
    for r in sorted(events):
        ans += (r - pr) * get_zero()
        for lc, rc, d in events[r]:
            lst.apply(lc, rc, d)
        pr = r
    return ans


h, w, qh, qw, n = list(map(int, input().split()))
blacks = list(list(map(int, input().split())) for _ in range(n))
ans = solve(h, w, qh, qw, n, blacks)
print(ans)

G - Many Repunit Sum 2

• 正整数 $N, M$ が与えられます。
• 正整数 $d$ に対し、$d$ 桁の repunit を整数 $\displaystyle\sum_{i = 0}^{d - 1} 10^i$ として定義します。
• 相異なるとは限らない $1$ 桁以上 $M$ 桁以下の repunit $N$ 個の和として表すことのできる整数の個数を $998244353$ で割った余りを求めてください。

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^9$
• 入力される値はすべて整数

「何を数えればいいか」をハッキリさせるのがまず難しく、 また、その数え上げも（FPSに慣れた人なら見えやすいかもしれないが）難しい。

まず、ある選び方において $N$ 個の repunit の桁 $d$ の多重集合を $S$ とすると、以下のように表せる。

• $\displaystyle \sum_{d \in S}\frac{10^d-1}{9}$

これは、定数項を外に出すと

• $\displaystyle \frac{1}{9}\sum_{d \in S}{10^d}-\frac{N}{9}$

なので結局、問題は以下に言い換えられる。

• $\sum_{d \in S}{10^d}$、つまり $10,100,1000,...,10^{M}$ の $M$ 個の数を $N$ 個使って何通りの数が作れますか
• さらに、桁を1つずつ下げて $1,10,100,...,10^{M-1}$ としても答えは変わらない。

以下、言い換えた問題を考えていく。

ある選び方を $C=(c_0,c_1,...,c_{M-1})$ で表し、$c_i$ は $10^i$ を採用した個数を表すとする。
$\sum_i c_i=N$ であるような $C$ から作れる整数の種類数を数えることになる。

異なる $C$ から同じ数ができてしまうのが厄介だが、10の冪なので repunit よりはまだ考えやすい。
$c_i$ 10個セットで $c_{i+1}$ 1個相当になる。 どこかの桁を1つ繰り上げ、どこかの桁を1つ繰り下げれば、個数が変わらず結果が同じになり、重複してしまう。

N=20, M=5
i   0   1   2   3   4
  ( 0,  2, 13,  0,  5)  ...  51320 が作れる
      ↙     ↘
  (10,  1,  3,  1,  5)  ...  51320 が作れる

こういうのは「“51320” を作るなら必ずこの $C$」というように、 結果と $C$ が一対一対応となるように正規化ルールを決め、 その正規化後の $C$ として有効なもののみを数えるのがよくある。

しかし、今回の場合、それがなかなか決めづらい。

なんとなく「繰り上げが可能になるので各 $c_i$ は $10$ 以上になってはいけない」 みたいな方針は見えるものの、

N=10  ( 0,  0, 10,  0,  0)    ← 繰り上げの代わりに繰り下げられるものがない

N=15  ( 0,  0, 10,  5,  0)    ← i を繰り上げる代わりに繰り下げられるものが i+1 しかなく、
                                 それを繰り下げると自分自身に戻ってきてしまう

N=20  ( 0,  0,  0,  0, 20)    ← 端の場合は、それ以上繰り上げることができない

のように様々な例外が発生してしまい、手に負えない。

ここで、「個数を同じにする」ことは一旦忘れ、 「結果 $\sum_i c_i10^i$」が変わらないという点だけに着目して、$C$ の正規化を考えることにする。

結果が同じ数になる $C$ は、桁の繰り上げ・繰り下げによって遷移できるものとなる。 繰り上げでは「下の桁が10減って上の桁が1増える」、 繰り下げでは「上の桁が1減って下の桁が10増える」のように、 結果が同じ数になる $C$ では、$\sum_i{c_i} \mod{9}$ が維持されることが分かる。

ある整数 $v$ に対し、 $\sum_i{c_i}$ が最も少なくなるのは、明らかに以下の制約を満たす $C$ であり、これは一意に決まる。

• $i=0,...,M-2$ に対して $0\le c_i \le 9$
• $i=M-1$ は上限無し。$0 \le c_i$

M=5  v=140320  →  (0, 2, 3, 0, 14)

$v$ に対して総和が最小になる $C$ を考え、その $\sum_i{c_i}$ を $T$ とする。
以下を満たすなら、$v$ は $N$ 個の10冪の和として表せるといえる。

• $T \le N$
  • $\sum_i{c_i}$ は、$T$ から減らすことはできない
• $T \equiv N \mod{9}$
  • $\sum_i{c_i}$ は、任意の桁を繰り下げることで、9ずつ好きに増やすことができる
• $v \ge N$
  • 全てを $c_0$ に落としきっても、まだ $\sum_i{c_i}$ が $N$ 個に足りてない場合は不可
  • 全てを $c_0$ に落としきったときの $\sum_i c_i$ は当然、$v$ である

$v \ge N$ の条件は、最後に $\lfloor \frac{N}{9} \rfloor$ を答えから除けば良いので、上2つの条件を考えればよい。

まとめると、

• $i=0,...,M-2$ に対して $0\le c_i \le 9$
• $i=M-1$ は上限無し。$0 \le c_i$
• $\sum_i{c_i} \le N$
• $\sum_i{c_i} \equiv N \mod{9}$

を満たすような $C$ を数えれば、答えが導ける。

$\sum_i c_i$ を $x$ の指数とした形式的冪級数を使うと、以下のような式になる。

• $(1+x^1+...+x^9)^{M-1}(1+x^1+x^2+...)$

この $x^i$ の係数が、前項の数え上げ対象の上2つ

• $i=0,...,M-2$ に対して $0\le c_i \le 9$
• $i=M-1$ は上限無し。$0 \le c_i$

を満たすような $C$ の個数となるので、これの $x^{N},x^{N-9},x^{N-18},...$ の係数の総和が、求めたいものとなる。

$M$ が巨大だが、答えを求めるのに必要なのは先頭 $N$ 個の値だけなので、計算途中で適宜切り詰めてよい。

$(1+x^1+...+x^9)^{M-1}$ はダブリングで畳み込み、最後にもう1項を畳み込めば、答えが求められる。

または、以下の変換

• $(1+x^1+...+x^9)=\dfrac{1-x^{10}}{1-x}$
• $(1+x^1+...)=\dfrac{1}{1-x}$

を使えば、求めるものは $\dfrac{(1-x^{10})^{M-1}}{(1-x)^M}$ となり、 分子は単純な二項係数、分母は負の二項係数となるので、それぞれ第 $N$ 項までを求めた結果を畳み込めば、1回で求められる。

Python3

import numpy as np


def convolve(f, g):
    fft_len = 1
    true_len = len(f) + len(g) - 1
    while fft_len < true_len:
        fft_len <<= 1

    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
    Fh = Ff * Fg

    h = np.fft.irfft(Fh, fft_len)
    h = np.rint(h).astype(np.int64)

    return h[:true_len]


def convolve_mod(f, g, p):
    f1, f2 = np.divmod(f, 1 << 15)
    g1, g2 = np.divmod(g, 1 << 15)

    a = convolve(f1, g1) % p
    c = convolve(f2, g2) % p
    b = (convolve(f1 + f2, g1 + g2) - (a + c)) % p

    h = (a << 30) + (b << 15) + c
    return h % p


def solve(n, m):
    MOD = 998244353
    num = [0] * (n + 1)
    num[0] = 1
    for i in range(10, n + 1, 10):
        k = i // 10
        num[i] = -1 * num[i - 10] * (m - k) * pow(k, -1, MOD) % MOD
    dnm = [0] * (n + 1)
    dnm[0] = 1
    for i in range(1, n + 1):
        dnm[i] = dnm[i - 1] * (m + i - 1) * pow(i, -1, MOD) % MOD
    num = np.array(num, dtype=np.int64)
    dnm = np.array(dnm, dtype=np.int64)
    result = convolve_mod(num, dnm, MOD)
    ans = 0
    for i in range(n, -1, -9):
        ans += result[i]
    ans -= n // 9
    ans %= MOD
    return ans


def naive(n, m):
    from itertools import combinations_with_replacement
    cond = [10 ** i for i in range(m)]
    result = set()
    for use in combinations_with_replacement(cond, n):
        result.add(sum(use))
    return len(result)


def check():
    n = 15
    m = 3
    ans1 = solve(n, m)
    ans2 = naive(n, m)
    print(f'{ans1=} {ans2=}')


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