第六回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 201）A,B,C,D,E問題メモ

第六回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 201）

A - CatCoder Double Contest

問題文

$2222$ 年の CatCoder では、CatCoder Double Contest（以下、C2C と略します）を開催することになりました。
いま、問題案を持っている writer が $N$ 人います。
各 writer の問題案は難易度によって Hard, Medium, Easy の $3$ 種類に分類されており、$i$ 人目の writer が持っている Hard, Medium, Easy の問題案の個数はそれぞれ $A_i,B_i,C_i$ です。
各 C2C では Div.1, Div.2 の $2$ 部門を同時に $1$ つずつ開催します。それぞれの部門の開催に必要な問題案は以下の通りです。
- Div.1：同じ writer の Hard, Medium の問題案を $1$ つずつ
- Div.2：同じ writer の Medium, Easy の問題案を $1$ つずつ
ここで、Div.1, Div.2 の writer は必ずしも同じである必要がない点に注意して下さい。また、各問題案は高々 $1$ 回の C2C の $1$ つの部門にしか使用出来ません。

C2C を最大で何回開催出来るかを求めて下さい。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

制約

$1 \le T \le 10^5$
$1 \le N \le 2 \times 10^5$
$1 \le A_i,B_i,C_i \le 10^9$
全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
入力される値は全て整数

解法

$B$ 個あるMediumがどちらのDivでも使えるので、どっちで使うかが問題となる。

各writerの問題を、「Div1確定セット」「Div2確定セット」「どっちか一方のみに使えるセット」に分ける。

$d_1$ Div1確定: $\min(A_i, B_i-C_i)$
- $A$ と、「$C$ と最大限組にした上で残っている $B$」の小さい方。
$d_2$ Div2確定: $\min(C_i, B_i-A_i)$
- $C$ と、「$A$ と最大限組にした上で残っている $B$」の小さい方。
$d_3$ どちらか: $\min(A_i+C_i, B_i)-d_1-d_2$

全writerで、$d_1,d_2,d_3$ をそれぞれ合計したものを $D_1,D_2,D_3$ とし、 $D_3$ をいい具合にDiv1,Div2に分配すればよい。

Python3

def solve(n, writers):
    div1 = 0
    div2 = 0
    free = 0
    for a, b, c in writers:
        d1 = max(0, min(a, b - c))
        d2 = max(0, min(c, b - a))
        div1 += d1
        div2 += d2
        free += max(0, min(a + c, b) - d1 - d2)
    diff = abs(div1 - div2)
    if diff >= free:
        return min(div1, div2) + free
    return min(div1, div2) + (diff + free) // 2


t = int(input())
for _ in range(t):
    n = int(input())
    abc = [tuple(map(int, input().split())) for _ in range(n)]
    ans = solve(n, abc)
    print(ans)

B - Binary Knapsack

問題文

$1,2,\dots,N$ の番号がついた $N$ 個の品物があります。
品物 $i$ の重みは $2^{X_i}$ で価値は $Y_i$ です。
重みの和が $W$ 以下になるように品物を $0$ 個以上選ぶとき、価値の和としてありうる最大値を求めて下さい。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

制約

$1 \le T \le 10^5$
$1 \le N \le 2 \times 10^5$
$1 \le W \le 10^{18}$
$0 \le X_i \lt 60$
$1 \le Y_i \le 10^9$
全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
入力される値は全て整数

解法

ナップサックに見えて貪欲解法。

全ての重みについて、価値 $0$ の品物が無限にあるとし、重みの和をちょうど $W$ にすると考える。

たとえば $W=13$（2進数で1101）の場合、$X_i=0$（重み $1$）の品物は絶対に1つ使う。
$X_i \ge 1$ の品物をどう組み合わせても、絶対に $1$ の端数は残るため。
よって、$X_i=0$ の中で価値最大の1つをまずは確定させてよい。

残りの $X_i=0$ の品物は、2個1組として $X_i=1$ が1つと考えてよい。
この時も、より上の桁で使うなら価値の高い方から使うので、価値の高い方からペアにしていく。
1個余る品物があったら、最初に仮定した価値0の品物と組み合わせると考える。

つまり、以下を $x=0,1,2,...$ と小さい方から繰り返せばよい。

$X_i=x$ の品物を価値の高い順にソートする
$W$ で $x$ bit目が立っている場合
- 1番目に価値が高いものを採用確定し、$(2,3),(4,5),...$ 番目に価値が高いものをペアにして $X_i=x+1$ の品物1つとする
$W$ で $x$ bit目が立っていない場合
- $(1,2),(3,4),...$ 番目に価値が高いものをペアにして $X_i=x+1$ の品物1つとする

計算量は、$X_i=0$ の品物が大量にあり多くの品物が何回も繰り上がるときが最も大きくなるが、その場合でも $N+\frac{N}{2}+\frac{N}{4}+...$ なので全体 $O(N)$ の処理である。
各 $x$ でのソートが発生するため、$O(N \log{N}+D)$ となる。

Python3

def solve(n, w, items):
    items_by_weight = [[] for _ in range(61)]
    for x, y in items:
        items_by_weight[x].append(y)
    ans = 0
    for i in range(60):
        ibw = items_by_weight[i]
        ibw.sort(reverse=True)
        ibw.append(0)
        if w & (1 << i):
            ans += ibw[0]
            for j in range(1, len(ibw) - 1, 2):
                items_by_weight[i + 1].append(ibw[j] + ibw[j + 1])
        else:
            for j in range(0, len(ibw) - 1, 2):
                items_by_weight[i + 1].append(ibw[j] + ibw[j + 1])
    return ans


t = int(input())
for _ in range(t):
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(n)]
    ans = solve(n, w, items)
    print(ans)

C - Prefix Covering

問題文

どの文字も 'A' または 'B' であるような空でない文字列を AB 文字列と呼ぶことにします。
AB 文字列からなる集合 $X$ が次を満たすとき、良い集合であるということにします。
- 長さ $10^{100}$ であるような AB 文字列は、必ずある $X$ の要素を接頭辞に持つ。

相異なる AB 文字列 $S_1, S_2, \ldots, S_N$ が与えられます。
各 $k=1,2,\ldots,N$ について、集合 $\lbrace S_1,S_2,\ldots,S_k\rbrace$ の部分集合であって良い集合であるものの個数を $998244353$ で割った余りを求めて下さい。

制約

$1\leq N\leq 2\times 10^5$
$S_1, S_2, \ldots, S_N$ は相異なる AB 文字列
$\sum_{1\leq i\leq N}|S_i|\leq 5\times 10^5$

解法

$S=\{S_1,S_2,...,S_k\}$ とする。

問題文の意味がちょっと取りづらいが、要は、以下のようなTrieがあったとして、

        ○
    A／    ＼B       ●: S に存在する文字列
   ○        ●
 A／＼B    A／＼B
 ●  ○    ○  ○
A/\BA/\B  A/\BA/\B
○○●○  ○●○○

「『●に当たらずに下まで抜けられる』ようなルートが存在しないような●の集合」が、良い集合となる。
例えば上の例は、ABB… が下まで抜けられてしまうため、$S$ は良い集合ではない。

Trieとセグメント木を混ぜ合わせたようなデータ構造で解くことを考える。

各ノードが以下の情報を持っていれば、セグメント木の要領で、2つの子の情報から自身の情報を計算できる。

$f_v$: 自身が●かどうかフラグ
$c_v$: 自身の部分木以下にある●の個数
$b_v$: 自身の部分木以下にある●の選び方で、ルートを封鎖するようなものの個数

$f_v,c_v$ は簡単なので、$b_v$ の計算方法を考える。

自身が●でない（$f_v=$false）場合、左右の子を $l,r$ として、単純に以下のようになる。

$b_v=b_l \times b_r$

自身が●（$f_v=$true）の場合、「自身を部分集合に加えない」場合の選び方は上記と一致し、加えて「自身を部分集合に加える」場合は、それより下はどう選んでもいいので、

$b_v+=2^{c_l+c_r}$

となる。

これで、各 $S_i$ の追加時に $O(|S_i|)$ で情報を更新し、その時々の $b_{\mathrm{root}}$ が答えとなる。

静的なセグメント木で作るとノード数が多くなりすぎるため、動的セグメント木で実装すると、計算量は $O(\sum |S_i|)$ となる。

Python3

from dataclasses import dataclass


@dataclass
class TrieNode:
    left: 'TrieNode'  = None
    right: 'TrieNode' = None
    parent: 'TrieNode' = None
    terminal_count: int = 0
    fill_pattern: int = 0
    choice_pattern: int = 1


def solve(n, sss):
    MOD = 998244353

    pow2 = [0] * (500_001)
    pow2[0] = 1
    for i in range(1, 500_001):
        pow2[i] = pow2[i - 1] * 2 % MOD

    ans = []
    root = TrieNode()
    for s in sss:
        node = root
        for c in s:
            if c == 'A':
                if node.left is None:
                    node.left = TrieNode(parent=node)
                node = node.left
            else:
                if node.right is None:
                    node.right = TrieNode(parent=node)
                node = node.right

        node.terminal_count += 1
        while True:
            fill_left = 0 if node.left is None else node.left.fill_pattern
            fill_right = 0 if node.right is None else node.right.fill_pattern
            choice_left = 1 if node.left is None else node.left.choice_pattern
            choice_right = 1 if node.right is None else node.right.choice_pattern
            tmp = fill_left * fill_right % MOD
            if node.terminal_count > 0:
                tmp += (pow2[node.terminal_count] - 1) * choice_left * choice_right % MOD
            node.fill_pattern = tmp % MOD
            node.choice_pattern = pow2[node.terminal_count] * choice_left * choice_right % MOD
            if node is root:
                break
            node = node.parent

        ans.append(root.fill_pattern)

    return ans


n = int(input())
sss = [input() for _ in range(n)]
ans = solve(n, sss)
print('\n'.join(map(str, ans)))

D - Match, Mod, Minimize

問題文

長さ $N$ の非負整数列 $A=(A_1,A_2,\dots ,A_N),B=(B_1,B_2,\dots ,B_N)$ と正整数 $M$ が与えられます。
$A$ の要素を自由に並び替えることが出来るとき、$\max_{1\le i\le N} ((A_i+B_i) \bmod M)$ としてありうる最小値を求めて下さい。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

制約

$1 \le T \le 10^5$
$1 \le N \le 3 \times 10^5$
$1 \le M \le 10^9$
$0 \le A_i,B_i \lt M$
全てのテストケースにおける $N$ の総和は $3 \times 10^5$ 以下
入力される値は全て整数

解法

単純そうだが、上手い言い換えを挟まないとなかなか $O(N^2)$ から減らない。

もし、MODが無ければ答えは簡単で、$A$ の昇順と $B$ の降順を対応づけたものが最善のペアとなる。
（そうでないペアの作り方があったとして、上記の対応に組み替えて損しないことが示せる）

modを考慮する場合、制約から、$A_i+B_i$ は、$0$ 以上 $2M$ 未満となる。
$(A_i+B_i) \bmod{M}$ は、$0 \le A_i+B_i \lt M$ の時 $A_i+B_i$、$M \le A_i+B_i \lt 2M$ の時 $A_i+B_i-M$ となる。

和が $M$ 以上 $2M$ 未満になることを、「繰り上がる」と表現することにする。

ある最適解を実現するペア分けがあったとして、各ペアは「繰り上がるペア」と「繰り上がらないペア」に分けられる。
このうち、「繰り上がらないペア」は、modを考慮しない場合と同じく、損しない組み替えを重ねることで繰り上がらないペアの中で $A$ の昇順と $B$ の降順を対応づけるように組み替えることができる。

   繰り上がらないペア
A  ○  ○   ○  ○
     ＼_ \ / _／
         -X-
     ／~ / \ ~＼
B  ○  ○   ○  ○

繰り上がるペアでも似たような組み替えは成り立ちそうなのだが、組み替えた結果、繰り上がらないペアに変化するパターンがあり、必ずしも「損しない」組み替えとなる保証がない。
このあたりの証明を詰め切れなかった。

$B'_i = (-B_i) \mod{M}$ とした上で、 $A_i+B_i$ を $A_i-B'_i$ と言い換えると少し見通しが良くなる。

この場合、$A_i \lt B'_i$ ならmodの結果が $M+A_i-B'_i$ となるので、あらかじめいくつかの $A_i$ に $M$ を足しておき、全て $A_i \ge B'_i$ となるような組を作ることを考える。

$M$ を足した後では、$A,B'$ の昇順にマッチングするのが明らかに最適である。
問題は、どのように $M$ を足す数と要素を選ぶべきか。

結論から言うと、条件を満たすまで $A$ の中の最小の数に $M$ を足す、ということを繰り返して問題ない。

略証

$A,B'$ を昇順ソート済みとして、たとえば ①$A_1$ ではなく ②$A_3$ に $M$ を足した後、再び昇順に並べた場合

A1 A2 A3 A4 A5    →①  A2 A3 A4 A5 A1+M
B1 B2 B3 B4 B5          B1 B2 B3 B4 B5
                        ~~~~~       ~~~~
                  →②  A1 A2 A4 A5 A3+M
                        B1 B2 B3 B4 B5
                        ~~~~~       ~~~~

$i=3$ より左の部分と、末尾の部分のペアに差が生じる。

$i=3$ より左の、①の $A_2-B'_1$ や $A_3-B'_2$ の部分は、 ②の $A_1-B'_1$ や $A_2-B'_2$ より大きくなるが、 $0 \le B'_i \lt M$ を踏まえると、取り得る最大値は $A_2,A_3$ である。

一方、末尾の②の $A_3+M-B'_5$ の部分は、$B'_5 \lt M$ よりかならず $A_3$ より大きい。

よって、①をおこなったことによって $A_i-B'_i$ の最大値が増加したとしても、その場合は②でそれ以上、増加してしまうことが言える。

よって、$A$ の小さい方から何個に $M$ を足せば、全て $A_i \ge B'_i$ となるかがわかればよい。

$A$ の末尾に、$A_1+M, A_2+M,...,A_N+M$ をこの順に加えたものを $A'$ とする。
各 $B_i$ から、自身以上となる $A'_j$ の位置を二分探索で探す。
$d_i=\max(0,j-i)$ が、その $i$ にとって、少なくとも $M$ を足さなければならない個数の最小値となる。
$\max_i d_i$ が、最適な $M$ を足す個数となる。

最適なシフト数が分かれば、実際に試して答えが求められる。

計算量は $O(N \log{N})$ となる。

Python3

def solve(n, m, aaa, bbb):
    bbb = [-b % m for b in bbb]
    aaa.sort()
    bbb.sort()
    aaa += [a + m for a in aaa]

    max_shift = 0
    j = 0
    n2 = n * 2
    for i in range(n):
        while j < n2 and aaa[j] < bbb[i]:
            j += 1
        max_shift = max(max_shift, j - i)

    ans = 0
    for i in range(n):
        ans = max(ans, aaa[i + max_shift] - bbb[i])
    return ans


t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    aaa = list(map(int, input().split()))
    bbb = list(map(int, input().split()))
    ans = solve(n, m, aaa, bbb)
    print(ans)

E - Total Area of Bounding Boxes

問題文

$2$ 次元平面上に $1,2, \dots, N$ の番号がついた $N$ 個の点があります。
点 $i$ の座標は $(i,Y_i)$ です。
- なお、この問題では $Y=(Y_1,Y_2,\dots ,Y_N)$ は $(1,2, \dots ,N)$ の順列であることが保証されます。
$\lbrace \texttt{点} 1,\texttt{点} 2,\dots ,\texttt{点} N \rbrace$ の要素数 $2$ 以上の部分集合 $S$ 全てに対するバウンディングボックスの面積の総和を $998244353$ で割った余りを求めて下さい。
$S$ に対するバウンディングボックスとは、 $S$ に含まれる全ての点を内部または周上に含んでかつ $x$ 軸に平行な辺を持つような長方形のうち、面積が最小であるものを指します。

制約

$2 \le N \le 2 \times 10^5$
$Y$ は $(1,2, \dots ,N)$ の順列
入力される値は全て整数

解法

主客転倒で、「ある $1 \times 1$ のマスがバウンディングボックスに含まれるような点の部分集合の個数」を考える。

  
   A  ┃  ┃  B
━┿━┛─┗━┿━
  │  │■│  │
━┿━┓─┏━┿━
   C  ┃  ┃  D

あるマスの、左上、右上、左下、右下の領域を、それぞれ $A,B,C,D$ とする。
また、それぞれに含まれる点の個数を、$a,b,c,d$ とする。（太線の境界上の点も含む）

包除原理で考える。

全ての点の選び方 $2^N$。

「$AB$ だけから選ばれた場合」「$AC$ だけから選ばれた場合」「$BD$ だけから選ばれた場合」「$CD$ だけから選ばれた場合」は ■はバウンディングボックスに含まれない。

上記のうち、「$A$ だけから選ばれた場合」「$B$」「$C$」「$D$」は重複して引かれている。

上記のうち、「全てが選ばれない」状態は重複して加算されている。

以上をまとめると、以下が、■がバウンディングボックスに含まれる部分集合の個数である。

$2^N - 2^{a+b} - 2^{a+c} - 2^{b+d} - 2^{c+d} + 2^a + 2^b + 2^c + 2^d - 1$

$(N-1) \times (N-1)$ の全ての■についてこれを計算すれば答えとなる。

これ、1つ1つは加減算なので、かなり大胆にバラして考えられる。

$2^N$ と $-1$ は、どの■でも加算される
$2^{a+b}$ など、指数が2数の足し算となっている部分は、
- 例えば上から5行目の $N-1$ 個のマスはどのマスでも $2^{a+b}=2^5$ となる。
- 4方向それぞれ、同じ考え方ができるので4倍する。
- $(2^1+2^2+...+2^{N-1}) \times (N-1) \times 4$

ということで、厄介なのは $2^a,2^b,2^c,2^d$ の、指数が単独文字の項となる。

ひとまず、全ての■についての $2^a$ の合計を求めることを考える。$b,c,d$ も同様に考えられる。

   1  2  3  4  5    ←格子点の座標
    １ ２ ３ ４     ←マスのindex
1     '
2  '
3           '
4              '
5        '

  ↓
    １ ２ ３ ４
1    0' 1  1  1    各マスの a の値
2  ' 1  2  2  2    （N行目は存在しない点に注意）
3    1  2  2' 3
4    1  2  2  3'
5        '

これの、各 $2^a$ の総和を求めたい。

セグメント木で求められる。

載せるもの: (自身の管理する区間内の点の個数, 自身の管理する区間だけにおける各マスの $2^a$ の総和)

ちょっと2つめが言葉で説明しにくいが、

a: 1 2 2 3  3 4 5 5
            ~~~~~~~    ←この区間を表すノードの場合、
            0 1 2 2    ←区間外の点を考慮しないなら a はこうなってるはずで、
            1+2+4+4=11 ←その2^aの総和である11を持たせる。

a: 1 2 2 3  3 4 5 5
   ~~~~~~~~~~~~~~~~    ←左のノードとマージするとき、
                         左ノードにある点の個数が2個だとして、
           4+8+16+16=44  右ノードの値は一律 2^2 倍となる。
                         （後は左ノードの値をそのまま加算すればマージ完了）

$i=1,2,...$ の順に $(i,y_i)$ に点を打った状態に更新し、その都度、その列全体の $2^a$ の総和（要は、ルートノードの2つめの値）を加算していけばよい。

    １ ２ ３ ４
1    0' 1  1  1    各マスの a の値
2  ' 1  2  2  2
3    1  2  2' 3
4    1  2  2  3'
     v  v  v  v
     7 14 14 22  →  全体の 2^a の総和は 57

$2^a$ と $2^c$、$2^b$ と $2^d$ はそれぞれ、上からの累積和と下からの累積和でやることが似ているのでまとめてやると、i=1,2,…,N の順と $i=N,N-1,...,1$ の順の2回の走査で全て求められる。

これで、必要な情報が全て計算できた。

Python3

from atcoder.segtree import SegTree


def naive(n, yyy):
    MOD = 998244353
    INF = 1 << 60
    ans = 0
    for bitset in range(3, 1 << n):
        if bitset.bit_count() == 1:
            continue
        u, d, l, r = INF, -INF, INF, -INF
        for i in range(n):
            if bitset & (1 << i):
                l = min(l, i)
                r = max(r, i)
                u = min(u, yyy[i])
                d = max(d, yyy[i])
        ans += (d - u) * (r - l)
        ans %= MOD
    return ans


def solve(n, yyy):
    MOD = 998244353

    pow2 = [1]
    for _ in range(n):
        pow2.append(pow2[-1] * 2 % MOD)

    def merge(a, b):
        ca, fa, ba = a
        cb, fb, bb = b
        return (ca + cb, (fa + fb * pow2[ca]) % MOD, (ba * pow2[cb] + bb) % MOD)

    ans = (pow2[n] - 1) * (n - 1) * (n - 1) % MOD

    init = [(0, 1, 1)] * n
    init[0] = (0, 1, 0)
    init[n - 1] = (0, 0, 1)

    sgt = SegTree(merge, (0, 0, 0), init)
    sgt.set(0, (0, 1, 0))
    sgt.set(n - 1, (0, 0, 1))
    for y in yyy[:-1]:
        if y == 1:
            sgt.set(0, (1, 2, 0))
        elif y == n:
            sgt.set(n - 1, (1, 0, 2))
        else:
            sgt.set(y - 1, (1, 2, 2))
        res = sgt.all_prod()
        ans += res[1] + res[2]
        ans %= MOD

    sgt = SegTree(merge, (0, 0, 0), init)
    sgt.set(0, (0, 1, 0))
    sgt.set(n - 1, (0, 0, 1))
    for y in reversed(yyy[1:]):
        if y == 1:
            sgt.set(0, (1, 2, 0))
        elif y == n:
            sgt.set(n - 1, (1, 0, 2))
        else:
            sgt.set(y - 1, (1, 2, 2))
        res = sgt.all_prod()
        ans += res[1] + res[2]
        ans %= MOD

    for i in range(1, n):
        ans -= (n - 1) * pow2[i] * 4
        ans %= MOD

    return ans


def test():
    import random
    n = 6
    for _ in range(100):
        yyy = list(range(1, n + 1))
        random.shuffle(yyy)
        ans1 = solve(n, yyy)
        ans2 = naive(n, yyy)
        if ans1 != ans2:
            print(f'ERROR! {yyy=} {ans1=} {ans2=}')


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

目次

第六回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 201）A,B,C,D,E問題メモ

A - CatCoder Double Contest

問題文

制約

解法

B - Binary Knapsack

問題文

制約

解法

C - Prefix Covering

問題文

制約

解法

D - Match, Mod, Minimize

問題文

制約

解法

E - Total Area of Bounding Boxes

問題文

制約

解法