ARC 161

Sun, Jul 13, 2025

A. Make M

https://atcoder.jp/contests/arc161/tasks/arc161_a

解説 AC.

方針はあっていたが実装ミスした。

rep(i, v.size()) {
    v.pop_back();
}

v の中身を全部舐めるために上記のような書き方をしてしまったが、これだと i がインクリメントされるのに対して上限の v.size() が減っていくため v 全体を舐められていなかった。 while (v.size()) のようにするか、予め size の値を保存にしてからループを回す必要があった。

$A$ をソートして前半半分を奇数番目の数字に、後半半分を偶数番目の数字にする。順番はソートされたままの状態にする。このときに、M型になるか判定すればよい。

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

    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];
    sort(all(A));

    vll f, b;
    rep(i, ceil(N, 2)) f.push_back(A[i]);
    rep2(i, ceil(N, 2), N) b.push_back(A[i]);

    int ok = 1;
    while (b.size()) {
        if (f.back() < b.back()) {
            f.pop_back();
            b.pop_back();
        } else {
            ok = 0;
            break;
        }
    }

    yesno(ok);
}

B. Exactly Three Bits

https://atcoder.jp/contests/arc161/tasks/arc161_b

自力 AC.

$N < 7$ のときはどうやっても 3 bit 立てられないので -1 を出力する。

$N \geq 7$ のとき

(i) 立っている bit 数が 3 以上のとき

上位 bit から3個残し他の bit を折ればよい。

(ii) 立っている bit 数が 3 未満のとき

$N$ の立っている bit 数が 3 以上になるまで $N$ をデクリメントする。多くても 3 回のデクリメントで立っている bit 数を3 以上にできる。この状態にしてから (i) の操作を行えばよい。

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

    int t;
    cin >> t;
    rep(i, t) {
        ll N;
        cin >> N;

        if (N < 7) {
            cout << -1 << '\n';
            continue;
        }

        while (__builtin_popcountll(N) < 3) N--;

        ll cnt = __builtin_popcountll(N);
        ll rm = cnt - 3;
        rep(i, 60) {
            if (rm == 0) break;
            if (N >> i & 1) {
                N ^= 1ll << i;
                rm--;
            }
        }

        cout << N << '\n';
    }
}

解説読んで理解した解法

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

    vll cand;
    rep(i, 60) rep2(j, i + 1, 60) rep2(k, j + 1, 60) {
        ll tmp = 0;
        tmp += 1ll << i;
        tmp += 1ll << j;
        tmp += 1ll << k;
        cand.push_back(tmp);
    }
    sort(all(cand));

    int t;
    cin >> t;
    rep(i, t) {
        ll N;
        cin >> N;

        auto it = upper_bound(all(cand), N);
        if (it == cand.begin()) {
            cout << -1 << endl;
        } else {
            cout << *prev(it) << endl;
        }
    }
}