問題

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(a));
    reverse(all(a));
    ll ok = 1;
    ll ng = n+1;
 
    while(abs(ok-ng)>1) {
        ll mid = (ok+ng)>>1;
        ll sa=0;
        ll sp=0;
        rep(i,mid){
            sa+=a[i];
            sp+=primes[i];
        }
        if(sa>=sp)ok=mid;
        else ng=mid;
    }
    cout << n-ok << '
';
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t=1;
    cin >> t;
    while(t--)solve();
}

時間計算量

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

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

Footnotes

1. エラトステネスの篩の気持ちになるとわかりやすそう ↩

2. $A$は大きくあって欲しいので。 ↩