ARC 149

Fri, Mar 28, 2025

A. Repdigit Number

https://atcoder.jp/contests/arc149/tasks/arc149_a

B. Two LIS Sum

https://atcoder.jp/contests/arc149/tasks/arc149_b

実験していて $A_i$ で sort して $B_i$ の LIS を求めるだけで良さそうだなと思って実装したら AC した。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<pair<int, int>> ps(n);
    rep(i, n) {
        int x;
        cin >> x;
        ps[i].first = x;
    }
    rep(i, n) {
        int x;
        cin >> x;
        ps[i].second = x;
    }

    sort(all(ps));

    ll ans = n;
    vint v(n + 1, INF);
    rep(i, n) {
        auto it = upper_bound(all(v), ps[i].second);
        *it = ps[i].second;
    }

    ans += lower_bound(all(v), INF) - v.begin();
    cout << ans << endl;
}