ABC 393

Table of Contents

D - Swap to Gather

なんとなく中央の 1 に寄せると良さそうという雰囲気で実装して AC してしまった

void solve() {
    int N;
    string S;
    cin >> N >> S;

    vint ids;
    rep(i, N) {
        if (S[i] == '1')
            ids.push_back(i);
    }

    ll ans = 0;
    int mid = ids[ids.size() / 2];
    int zid = mid + 1;
    for (int i = mid + 1; i < N; i++) {
        while (S[zid] == '1' && zid < N)
            zid++;
        if (i <= zid)
            continue;
        if (S[i] == '1') {
            ans += i - zid;
            swap(S[i], S[zid]);
        }
    }

    zid = mid - 1;
    for (int i = mid - 1; i >= 0; i--) {
        while (S[zid] == '1' && zid >= 0)
            zid--;
        if (zid <= i)
            continue;
        if (S[i] == '1') {
            ans += zid - i;
            swap(S[i], S[zid]);
        }
    }
    cout << ans << endl;
    // cout << S << endl;
}

E - GCD of Subset

愚直に全ての $A_i$ についての約数を調べて出現回数をメモって、各 $i$ に対して $A_i$ の約数のうち出現回数が $K$ を超えている中で最大のものを出力とすると TLE ぎりぎりだがなんとか AC できた。 しかし、どうやら想定解ではなかったらしい。

実際の提出コード

vll sieve((int)1e6 + 5, -1);

vector<pair<int, int>> factor(int x) {
    vector<pair<int, int>> res;
    while (x != 1) {
        ll cnt = 0;
        ll d = sieve[x];
        while (x % d == 0) {
            x /= d;
            cnt++;
        }
        res.push_back({d, cnt});
    }

    return res;
}

vvint memo((int)1e6 + 5);

vint divs(int x) {
    if (memo[x].size() != 0)
        return memo[x];
    auto facs = factor(x);
    vint res = {1};
    for (auto [d, cnt] : facs) {
        int n = res.size();
        rep(i, n) {
            int m = 1;
            rep(j, cnt) {
                m *= d;
                res.push_back(res[i] * m);
            }
        }
    }

    return memo[x] = res;
}

void solve() {
    int n, k;
    cin >> n >> k;
    vint a(n);
    rep(i, n) cin >> a[i];

    for (int i = 2; i < (int)1e6 + 5; i++) {
        for (int j = i; j < (int)1e6 + 5; j += i) {
            if (sieve[j] == -1)
                sieve[j] = i;
        }
    }

    vint cnt((int)1e6 + 5, 0);
    for (int x : a) {
        vint v = divs(x);
        for (int y : v)
            cnt[y]++;
    }

    vint sorted((int)1e6 + 5, 0);

    for (int x : a) {
        if (sorted[x])
            continue;
        sort(rall(memo[x]));
        sorted[x] = 1;
    }

    for (int x : a) {
        for (int y : memo[x]) {
            if (cnt[y] >= k) {
                cout << y << endl;
                break;
            }
        }
    }
}

模範

void solve() {
    int n, k;
    cin >> n >> k;

    vint a(n);
    rep(i, n) cin >> a[i];

    int mx = *max_element(all(a));
    vint num(mx + 1);

    for (int x : a)
        num[x]++;

    vint cnt(mx + 1, 0);
    rep2(i, 1, mx + 1) {
        for (int j = i; j <= mx; j += i) {
            cnt[i] += num[j];
        }
    }

    vint ans(mx + 1, 0);
    rep2(i, 1, mx + 1) {
        if (cnt[i] >= k) {
            for (int j = i; j <= mx; j += i) {
                ans[j] = i;
            }
        }
    }

    for (int x : a)
        cout << ans[x] << endl;
}

F - Prefix LIS Query

普通の LIS をしつつ $R_i$ が昇順の順でクエリを処理する。

void solve() {
    int n, q;
    cin >> n >> q;
    vint a(n);
    rep(i, n) cin >> a[i];
    vector<tuple<int, int, int>> qs;
    rep(i, q) {
        int r, x;
        cin >> r >> x;
        qs.push_back({r, x, i});
    }

    sort(all(qs));

    vint lis(n + 1, INF);
    int k = 0;  // LIS の計算で使う要素の index
    vint ans(q);
    for (auto [r, x, id] : qs) {
        for (int i = k; i < r; i++) {
            *lower_bound(all(lis), a[i]) = a[i];
        }
        k = r;

        int d = upper_bound(all(lis), x) - lis.begin();
        ans[id] = d;
    }

    for (int x : ans)
        cout << x << endl;
}