問題

link

解法

残す値の個数の最大値がもとまれば、消す値の個数の最小値がわかるので、前者を考えることにする。

この問題において、数列$A$の値の総和と所持しているお金の合計は一定である。つまり、目標の数列$B$があって、$\sum A \geq \sum B$であるならば数列Bを構成可能であると言える。また、「長さ$x$のいい数列$B$であって、総和を最小とするような数列は何か？」を考えると、これは素数を小さい方から$x$個並べた列である¹。

よって、以下の問題を高速に解くことができれば元の問題が解ける。なお、$A$は降順にソートされている²とし$B$は素数を小さい方から並べた数列であるとする。

以下を満たす$x$の最大値を求めよ。 $\sum_{i=1}^x A_i \geq \sum_{i=1}^x B_i$

$A$も$B$もすでに決まっているので前から順に判定しても良いし、条件には単調性があるので二分探索を用いることもできる。

提出

vll primes=Eratosthenes(1e7);
 
void solve() {
    int n; cin >> n;
    auto a=i64_vec_IN(n);
    sort(all( 

時間計算量

エラトステネスの篩を前計算し、$M$を「$N$番目の素数」とする。

ソートがボトルネックとなり、$O(N\log N + M\log \log M)$時間となる。