ARC 191

Table of Contents

A - Replace Digits

https://atcoder.jp/contests/arc191/tasks/arc191_a

コンテスト中考えていたこと

$T$ を降順に sort して $S$ が大きくなる限りは $T$ の文字に置き換えていく。改変後の $S$ を $S^\prime$ とする。 余った文字はすでに置き換えた文字の元々あった場所より、余った文字の元々の index が小さければその文字を捨てる(捨てる文字を先に差し込んでからあとから置き換え対象の文字で上書きできるので捨てても問題ない)。それもできなかったら余った文字の中で元々の index が一番後ろとなるものを $S^\prime$ の最後の文字に置き換えればいいと思った。

提出して WA になった。

https://atcoder.jp/contests/arc191/submissions/62131491

このケースだと $S = 912, T = 111$ というケースにおいて $S = 911$ となってしまうが $S$ の 1 のところに $T$ の 1 で置き換えることで最終的に $S = 912$ のままにできる。

よって index の考慮に加えてすでに $S$ の中にある文字も捨てて良い。これで AC した

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

    vector<pair<char, int>> t;
    rep(i, M) t.push_back({T[i], i});
    sort(rall(t));

    set<int> used;
    int i = 0, j = 0;
    while (i < N && j < M) {
        if (S[i] < t[j].first) {
            S[i] = t[j].first;
            used.insert(t[j].second);
            i++;
            j++;
        } else {
            i++;
        }
    }
    if (j < M) {
        set<char> freq;
        for (char c : S)
            freq.insert(c);
        rep2(k, j, M) {
            if (freq.count(t[k].first)) {
                used.insert(t[k].second);
                continue;
            }
            auto it = used.lower_bound(t[k].second);
            if (it != used.end()) {
                continue;
            }

            S[N - 1] = t[k].first;
            used.insert(t[k].second);
        }
    }
    cout << S << endl;
}

https://atcoder.jp/contests/arc191/submissions/62132625

解説を読んで

余った文字種の元々の index と置き換えた文字の元々の index の位置を比較して余った文字を捨ててよいかどうかを判断していたが、結局 $T$ の最後の文字を置き換えるところに置き換えておけばいらない文字は全て捨てられるので都度 index を比較する必要はなかった。 $T$ の最後の文字が $S^\prime$ にすでに使われているか、$S^\prime$ の中に含まれていればそのままでよい。そうでなかった場合は $T$ の最後の文字で $S^\prime$ の最後の文字を置き換える

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

    string t = T;
    sort(rall(t));

    int i = 0, j = 0;
    while (i < N && j < M) {
        if (S[i] < t[j]) {
            S[i] = t[j];
            i++;
            j++;
        } else {
            i++;
        }
    }

    int ok = 0;
    for (char c : S) {
        if (c == T.back())
            ok = 1;
    }
    if (!ok)
        S.back() = T.back();
    cout << S << endl;
}

B - XOR = MOD

コンテスト中には解いてない。後日緑 diff の問題練習で解いた。

小さい数で実験して $N \leq X \leq 2N-1$ の範囲であることはわかった。 あとは $N$ を2進数表記したときに $0$ のなっているところに $K-1$ を2進数表記したものを当てはめていくと実験結果と同じになりそうだったのでその方針で実装したら AC した。

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

    auto cal = [&](ll n, ll k) -> void {
        int rank = 0;
        ll t = n;
        while (t) {
            rank++;
            t /= 2;
        }

        int nzero = 0;
        rep(i, rank) {
            if (!((n >> i) & 1)) {
                nzero++;
            }
        }

        k--;
        if (k >= (1ll << nzero)) {
            cout << -1 << endl;
            return;
        }

        ll ans = n;
        rep(i, 32) {
            if ((n & (1ll << i)) == 0 && k) {
                if (k % 2 == 1)
                    ans |= (1ll << i);
                k /= 2;
            }
        }
        cout << ans << endl;
    };

    int t;
    cin >> t;
    rep(i, t) {
        ll n, k;
        cin >> n >> k;
        cal(n, k);
    }
}