ARC 182

Sat, Mar 22, 2025

A. Chmax Rush

https://atcoder.jp/contests/arc182/tasks/arc182_a

解説 AC

$i$ 番目の操作は、左操作か、右操作か、どちらでも良いかの3通りがある。 $i$ 番目の操作が左か右操作のいずれかに確定している場合はそれを実行しなければならないので、$2^\text{どちらの操作をしても良い回数}$ が答えとなる

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

    int n, q;
    cin >> n >> q;
    vint P(q), V(q);
    rep(i, q) {
        cin >> P[i] >> V[i];
        P[i]--;
    }

    // kind[i]: i 回目にどの操作を必要があるか
    // -1 左操作
    // 1  右操作
    // 0  どちらでも良い
    vint kind(q);

    auto change = [&](int i, int op) -> bool {
        if (kind[i] == 0) {
            kind[i] = op;
            return true;
        }
        if (kind[i] != op) {
            // 操作が矛盾
            return false;
        }
        return true;
    };

    rep(i, q) {
        rep2(j, i + 1, q) {
            if (V[i] <= V[j])
                continue;
            if (P[i] == P[j]) {
                cout << 0 << endl;
                return;
            }

            bool ok = true;
            if (P[i] < P[j]) {
                // i 番目の操作で左操作
                // j 番目の操作で右操作
                // をしなければならない
                ok = ok && change(i, -1);
                ok = ok && change(j, 1);
            }
            if (P[i] > P[j]) {
                // i 番目の操作で右操作
                // j 番目の操作で左操作
                // をしなければならない
                ok = ok && change(i, 1);
                ok = ok && change(j, -1);
            }
            if (!ok) {
                cout << 0 << endl;
                return;
            }
        }
    }

    mint two = 2;
    ll cnt = 0;
    rep(i, q) cnt += kind[i] == 0;
    cout << two.pow(cnt).val() << endl;
}

B. |{floor(A_i/2^k)}|

https://atcoder.jp/contests/arc182/tasks/arc182_b

解説 AC.

$2^{K-1}$ 未満の数字は考える必要がない。なぜなら2倍すれば種類数が増えるか変わらないかで減ることはないから。

$N \geq 2^{K-1}$ のとき

$[2^{K-1}, 2^K)$ の範囲にある数字の個数は $2^{K-1}$ であるから $[2^{K-1}, 2^K)$ の数字と足りない分は $2^K$ 未満の数で適当に埋めればよい。

$N < 2^{K-1}$ のとき

$[2^{K-1}, 2^K)$ の範囲にある数字から $N$ 個を選ぶが選び方を間違えると誤答する。選び方としては上位 bit が異なるように選ぶのが最適である。

1 から始め桁数を増やすときは 0 を増やすか 1 を増やすかの2択だが、既存のものに 0 を最下位 bit に付け加える操作を仕切った後に、1 を最下位 bit に加える操作をする。右 bit shift したときに残る数の種類数を増やしたいからこのような操作になる。

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

    vvll tp(31);
    tp[0].push_back(1);
    rep2(i, 1, 31) {
        ll cnt = 0;
        int ex = 0;
        rep(j, 2) {
            for (ll x : tp[i - 1]) {
                tp[i].push_back((x << 1) + j);
                cnt++;
                if (cnt > 2e5 + 5) {
                    ex = 1;
                    break;
                }
            }
            if (ex)
                break;
        }
    }

    auto cal = [&](ll n, ll k) -> void {
        vll ans;
        rep(i, n) {
            if (i < tp[k - 1].size())
                ans.push_back(tp[k - 1][i]);
            else
                ans.push_back(1);
        }
        print(ans);
    };

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