C - Mex of Subset Sum 解説 by evima
Below, for an integer sequence, its subsequence sum is the sum of elements of its subsequence.
We assume \(A_i\) is sorted in ascending order.
We define a set \(EX_i\) as the set of the non-negative integers at most \(S_i := A_1 + A_2 + ... + A_i\) that are not a subsequence sum of \((A_1, A_2, ..., A_i)\). For convenience, we set \(EX_0 = \{\}\) and consider calculating \(EX_i\) from \(EX_{i-1}\). Depending on the values of \(A\), \(EX_i\) might become quite a large set. However, until the smallest \(K\) integers belonging to \(EX_N\) are determined, it doesn’t grow too large, and we have \(|EX_i| \leq Ki\). Below, we will prove this inductively.
Considering \(EX_i\) with respect to \(EX_{i-1}\), we consider the following cases:
[1] When \(S_{i-1} < A_i\)
Due to the monotonicity of \(A\), the following cannot be a subsequence sum of \(A\):
- integers in \(EX_{i-1}\), and
- integers greater than or equal to \(S_{i-1} + 1\) and less than \(A_i\).
Furthermore, these are all of the elements of \(EX_N\) that are less than \(A_i\). The number of such integers is \(|EX_{i-1}| + A_i - S_{i-1} - 1\), and if this is greater than or equal to \(K\), the \(K\) integers we are seeking are determined (★).
Consider when it is less than \(K\). \(EX_i\) can be divided into the following three types of integers:
- integers in \(EX_{i-1}\),
- integers greater than or equal to \(S_{i-1} + 1\) and less than \(A_i\), and
- integers \(x\) greater than or equal to \(A_i\) and less than \(S_i\) satisfying \(x - A_i \in EX_{i-1}\).
The number of integers of the second and third types is \(|EX_{i-1}| + A_i - S_{i-1} - 1\), which we assumed to be less than \(K\), so we have \(|EX_i| \leq |EX_{i-1}| + K\).
[2] When \(A_i \leq S_{i-1}\)
Due to the monotonicity of \(A\), the following cannot be a subsequence sum of \(A\):
- integers less than \(A_i\) and in \(EX_{i-1}\).
Furthermore, this is all of the elements of \(EX_N\) that are less than \(A_i\). If the number of such integers is greater than or equal to \(K\), the \(K\) integers we are seeking are determined (★).
Consider when it is less than \(K\). \(EX_i\) can be divided into the following three types of integers:
- integers less than \(A_i\) and in \(EX_{i-1}\),
- integers \(x\) between \(A_i\) and \(S_{i-1}\), inclusive, satisfying \(x \in EX_{i-1}\) and \(x - A_i \in EX_{i-1}\), and
- integers \(x\) between \(S_{i-1} + 1\) and \(S_i\), inclusive, satisfying \(x - A_i \in EX_{i-1}\).
The first and second types of integers are elements of \(EX_{i-1}\), and their count is less than or equal to \(|EX_{i-1}|\). The number of the third type of integers, paying attention to \(x \in EX_{i-1} \iff S_{i-1} - x \in EX_{i-1}\), is the same as the number of the first type of integers. Since we assumed this to be less than \(K\), we have \(|EX_i| \leq |EX_{i-1}| + K\).
Therefore, as long as ★ does not happen and the answer is not confirmed, we have \(|EX_i| \leq |EX_{i-1}| + K\), and by induction, we can conclude that \(|EX_i| \leq Ki\).
Thus, if we print the answer immediately when ★ happens while maintaining \(EX_i\) straightforwardly, it takes \(O(N^2K\log {(NK)})\) time (if std::set
is used to maintain them).
(Modified the first draft written by GPT-4.)
投稿日時:
最終更新: