G - Strange Beauty

f:id:peroon:20210127062803p:plain

  • 計算量
    • Time LimitがシビアでTLEしていたので、各数字のカウントをmapからvectorにした
    • dpの箇所で各値の倍数を見ていくが、これは調和級数の和なので 1/1 + 1/2 + 1/3 + ... + 1/N = log(N) に収まる
void solve(){
  ll N;cin>>N;
  VI A(N);
  rep(i, N)cin>>A[i];
  SORT(A);
  ll max_value = A.back();

  VI C(max_value+1); // count
  for(ll a : A)C[a]++;

  VI B = A; // unique values
  auto it = unique(ALL(B));
  B.erase(it, B.end());

  VI exist(max_value+1);
  for(ll b : B)exist[b]=1;

  auto dp = C;
  ll max_group_size=MAX(dp);

  for(ll b : B){
    FOR(i,2,max_value+1){
      ll v = i*b;
      if(v>max_value)break;
      if(exist[v]){
        chmax(dp[v], dp[b]+C[v]);
        chmax(max_group_size, dp[v]);
      }
    }
  }
  ll ans = N-max_group_size;
  p(ans);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;cin>>N;
    while(N--)solve();
    
    return 0;
}

koboshiさん