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;

}