競技プログラミング日記

主に AtCoder の記事です

AtCoder Regular Contest 133B

 

ARC133B

拡張したLIS.

類題: 問題:ARC126B記事

実装
\(P\) のindex を回した方が楽. 倍数判定なので,エラトステネスの篩と同様にできるため. \(Q\) のindex を回すと,約数を列挙しないといけないとので, \(O(N^{\frac{1}{2}})\) が余分にかかる.

使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"


int main() {
  ll n;
  cin >> n;
  vll p(n), q(n);
  cinv(p);
  cinv(q);

  vll inv_q(n+1);
  rep(i,n){
    inv_q[q[i]] = i;
  }

  vll v;
  rep(i,n){ // index of p
    vll tmp;
    for(ll y = p[i]; y <= n; y += p[i]){
      ll j = inv_q[y];
      tmp.emplace_back(j);
    }
    sort(all(tmp), greater<ll>());

    v.insert(v.end(), all(tmp));
  }

  vll dp(v.size(), INFL);
  for(ll j: v){
    auto it = lower_bound(all(dp), j);
    *it = j;
  }
  cout << (lower_bound(all(dp), INFL) - dp.begin()) << endl;

  return 0;
}