ABC 234

Table of Contents

C - Happy New Year

問題

$K$ を2進数にしたときの 1 となっているところを 2 に置き換えたものが答え

void solve() {
    ll k;
    cin >> k;

    // n: bit が立っている最も大きい idx
    int n = 0;
    rep(i, 60) if ((k >> i) & 1) n = i;

    string ans = "";
    rep(i, n + 1) ans.push_back((k >> i) & 1 ? '2' : '0');
    reverse(all(ans));
    cout << ans << endl;
}

提出コード

D - Prefix K-th Max

$S = \{P_1, \cdots, P_K\}$ となる集合を考える. $K+1$ 番目以降の数は保存しておく必要がないので, $P_{K+1} > \min(S)$ ならば $\min(S)$ を取り除き, $P_{K+1}$ を追加. $P_{K+1} < \min(S)$ ならば $P_{K+1}$ は集合に入れずそのまま捨てる. 以降 $P_N$ まで同様の操作を行って, その時その時の $\min(S)$ を出力する.

Priority Queue を使うと高速に処理できる.

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> P(n);
    rep(i, n) cin >> P[i];

    priority_queue<int, vector<int>, greater<int>> pq;
    rep(i, k - 1) pq.push(P[i]);
    rep2(i, k - 1, n) {
        pq.push(P[i]);
        if (pq.size() > k)
            pq.pop();
        cout << pq.top() << endl;
    }
}

$\min(S)$ が更新されるのは限られているので priority_queue を使わずにこういう書き方もできる.

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> P(n);
    rep(i, n) cin >> P[i];

    vector<int> used(n + 1, 0);
    int m = INF;
    rep(i, k) {
        chmin(m, P[i]);
        used[P[i]] = true;
    }
    cout << m << endl;
    rep2(i, k, n) {
        if (m < P[i]) {
            used[P[i]] = true;
            used[m] = false;
            while (!used[m])
                m++;
        }
        cout << m << endl;
    }
}

提出コード

E - Arithmetic Number

問題

$X$ が高々18桁で等差数となるものが少ないので等差数を全列挙して $X$ 以上となるものを出力する.

void solve() {
    string X;
    cin >> X;

    int K = X.size();

    // K 桁の全ての等差数
    vector<string> cands;
    rep2(start, 1, 10) {
        rep2(d, -9, 10) {
            string x = "";
            rep(j, K) {
                int c = start + j * d;
                if (0 <= c && c <= 9)
                    x.push_back('0' + c);
            }
            if (x.size() == K)
                cands.push_back(x);
        }
    }

    sort(all(cands));
    cout << *lower_bound(all(cands), X) << endl;
}

提出コード