ABC 349

Table of Contents

D - Divide Interval

https://atcoder.jp/contests/abc349/tasks/abc349_d

証明せずに貪欲で AC した。

左端の数から始まる良い数列のうち最長のものを採用していく。 左端の数が $l = 2^i j$ とするとき、良い数列は次の通りである

長さ数列
$2^i$$S(2^i j, 2^i (j+1))$
$2^{i-1}$$S(2^{i-1} 2j, 2^{i-1} 2(j+1))$
$\vdots$
$1$$S(2^1 2^{i-1}j, 2^1 2^{i-1}(j+1))$
$0$$S(2^0 2^{i}j, 2^0 2^{i}(j+1))$

このうち $R$ を超えないもので最長のものを採用していく。

void solve() {
    ll l, r;
    cin >> l >> r;

    vector<pair<ll, ll>> ans;
    while (r - l >= 1) {
        ll cnt = 0;
        while ((l & (1LL << cnt)) == 0 && cnt <= 60)
            cnt++;

        while (l + (1LL << cnt) > r)
            cnt--;

        ans.push_back({l, l + (1LL << cnt)});
        l += 1LL << cnt;
    }

    cout << ans.size() << endl;
    for (auto [x, y] : ans) {
        cout << x << ' ' << y << endl;
    }
}