AtCoder Beginner Contest 321（ABC321）

atcoder.jp

Bondo416さんのサントリープログラミングコンテスト2023（AtCoder Beginner Contest 321）での成績：798位
パフォーマンス：1666相当
レーティング：1443→1468 (+25) :)#AtCoder #サントリープログラミングコンテスト2023（ABC321） https://t.co/tnxvAcUeaS

— ボンド@競プロ (@bond_cmprog) September 23, 2023

A - 321-like Checker

愚直に判定する
文字列で受け取ると少し楽

提出コード

void solve() {
    string N;
    cin >> N;
    bool ok = true;
    REP(i, (int)N.size() - 1) {
        if (N[i] <= N[i + 1]) ok = false;
    }
    cout << (ok ? "Yes" : "No") << endl;
}

B - Cutoff

毎回 $ S $ を生成、ソートしても間に合うので、$ 0 \leq x \leq 100 $ を全探索し条件を満たすかどうかを判定する

提出コード

void solve() {
    string S;
    cin >> S;
    int N = S.size();
    int ans = 1;
    REP(i, N) {
        REP(j, i + 1, N) {
            string t = "";
            REP(k, i, j + 1) t += S[k];
            int sz = t.size();
            bool ok = true;
            REP(k, sz / 2) {
                if (t[k] != t[sz - k - 1]) {
                    ok = false;
                    break;
                }
            }
            if (ok) chmax(ans, sz);
        }
    }
    cout << ans << endl;
}

C - 321-like Searcher

存在する321-like Number の数は、雑に見積もって $ 10! $、使う一桁の整数の集合を決めると並び方は一意に定まるので $ 2 ^ 10 $ となるので全通り作ってソートすれば良い

提出コード

void solve() {
    ll K;
    cin >> K;
    vector<ll> ans;
    queue<ll> q;
    REP(i, 1, 10) q.push(i);
    while (!q.empty()) {
        ll now = q.front();
        q.pop();
        ans.push_back(now);
        int last = now % 10;
        for (int i = last - 1; i >= 0; i--) {
            q.push(now * 10 + i);
        }
    }
    sort(ALL(ans));
    cout << ans[K - 1] << endl;
}

D - Set Menu

$ B $ は昇順に並んでいるものとする
$ A_i $ について、$ P - A_i $ より大きい最小の $ B _ {idx} $ を求める
そうすると、$ idx \times A_i \times + \sum _ {j = 0} \ ^ {idx} B _ j $ と $ P \times (M - idx) $ が答えに加算される
予め $ B $ についてソート、累積和を取っておき上記を二分探索で求めることで解くことができる

提出コード

void solve() {
    ll N, M, P;
    cin >> N >> M >> P;
    vector<ll> A(N), B(M);
    REP(i, N) cin >> A[i];
    REP(i, M) cin >> B[i];
    sort(ALL(B));
    vector<ll> cum(M + 1);
    REP(i, M) cum[i + 1] = cum[i] + B[i];
    ll ans = 0;
    dump(A);
    dump(B);
    REP(i, N) {
        ll idx = upper_bound(ALL(B), P - A[i]) - B.begin();
        ans += idx * A[i] + cum[idx];
        ans += P * (M - idx);
    }
    cout << ans << endl;
}

F - #(subset sum = K) with Add and Erase

クエリで与えられる $ x $ を$ a $ とする
FPSで考えると + の操作は $ (1 + x^a) $ の乗算、- の操作は $ (1 + x^a) $ の除算の操作になる
スパースな場合の乗算・除算を行うと各操作 $ O(K) $ となるので十分実行時間に間に合う

提出コード

void solve() {
    int Q, K;
    cin >> Q >> K;
    const int MAX = 5050;
    FPS<mint> f(MAX);
    f[0] = 1;
    while (Q--) {
        char q;
        int x;
        cin >> q >> x;
        vector<mint> nxt(MAX);
        if (q == '+') {
            if (x <= K) {
                vector<pair<int, mint>> g = {{0, 1}, {x, 1}};
                mul(f, g);
            }
        }
        else {
            if (x <= K) {
                vector<pair<int, mint>> g = {{0, 1}, {x, 1}};
                div(f, g);
            }
        }
        cout << f[K] << endl;
    }
}