Kazun の競プロ記録

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

AtCoder Beginner Contest 297 E問題 Kth Takoyaki Set

AtCoder ABC ABC297 E問題 500 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 個の正の整数 $A_1, \dots, A_N$ が与えられる. 正の整数全体の集合 $S$ を

$\displaystyle S:=\left \{ \sum_{i=1}^N s_i a_i \middle| s_1, \dots, s_n \in \mathbb{Z}_{\geq 0}, (s_1, \dots, s_n) \neq (0, \dots, 0) \right\}$

とする. このとき, $S$ の要素のうち, 小さい方から $K$ 番目の要素を求めよ.

制約

$1 \leq N \leq 10$
$1 \leq K \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$

解法

$S$ に含まれる $1$ 番目から $t$ 番目に小さい整数を順に $x_1, \dots, x_t$ として,

$\displaystyle x_t=\sum_{i=1}^N s_i A_i$

とすると, $S$ に含まれる $(t+1)$ 番目に小さい整数は $1$ 以上 $t$ 以下の整数 $u$ と $1$ 以上 $N$ 以下の整数 $j$ が存在して,

$\displaystyle \sum_{i=1}^N (s_i+\delta_{j,i}) A_i$

と表せる. ここで, $\delta_{\bullet, \bullet}$ はクロネッカーのデルタとする.

よって, $S$ に含まれる $(t+1)$ 番目に小さい整数の候補は高々 $(t+1)N$ 個である. 従って, その候補となる整数を集合で管理していけばよい.

また, $t$ 番目に小さい整数についてはその集合から最小値を削除した時の最小値に一致する.

従って, 計算量 $O(NK \log NK)$ 時間で解くことが出来た.