ECR178D - Array and GCD

#不変量 #貪欲法

問題

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 << '\n';
}

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)\) 時間となる。