Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 282 F問題 Union of Two Sets

AtCoder ABC282 ABC F問題 500 pts

問題

提出解答

問題の概要

インタラクティブ問題

次の2つの Phase を完遂せよ.

Phase 1

$N$ が与えられる.
$1$ 以上 $5 \times 10^4$ 以下の整数 $M$ を出力する.
$M$ 個の整数の組 $(l_1, r_1), \dots, (l_M, r_M)$ を出力する. ただし, $1 \leq l_i \leq r_i \leq N$ でなくてはならない.

Phase 2

$Q$ が与えられる.
以下を回行う. 回目は以下である.
- $L_q, R_q$ が与えられる.
- 以下を満たす $1$ 以上 $M$ 以下の整数 $a,b$ を出力する: $\{l_a, l_a+1, \dots, r_a\} \cup \{l_b, l_b+1, \dots, r_b\}=\{L, L+1, \dots, R\}$

制約

$1 \leq N \leq 4000$
$1 \leq Q \leq 10^5$
$1 \leq L_q \leq R_q \leq N$
$L_q, R_q$ は Phase 1 の出力から決定される.

解法

$X:=\{1,2, \dots, N\}$ の部分集合族 $\mathcal{A}$ を

$\mathcal{A}:=\{\{L, L+1, \dots, L+2^k-1\} \subset X \mid k \in \mathbb{N}, 2^k \leq N, L+2^k-1 \leq N \}$

とする. このとき, $M=\# \mathcal{A} \leq N \times (\left \lfloor \log_2 N \right \rfloor+1) \leq 4000 \times (11+1) \leq 48000$ であるから, $M \leq 5 \times 10^4$ の条件を満たす.

$\mathcal{A}$ の元は, $X$ の部分集合で, 長さが $2$ ベキであるような区間である.

$\{L_q, \dots, R_q\}$ に関するクエリを考える. $2^K \leq R_q-L_q+1$ となる最大の整数 $K$ を取ってきた時,

$\{L_q, \dots, L_q+2^K-1\}, \{R_q-(2^K-1), \dots, R_q\} \in \mathcal{A}$
$\{L_q, \dots, L_q+2^K-1\} \cup \{R_q-(2^K-1), \dots, R_q\} = \{L_q, \dots, R_q\}$

である.

なお, この問題は Sparse Table というデータ構造を背景とした問題である.