$2^{k} \le N \lt 2^{k+1}$ ならば $N \lt 2^{k} + 2^{k}$ になるネタ、結構見る！

問題概要

数列 $a_{1}, a_{2}, \dots, a_{N}$ があって、初期状態では $a_{i} = i$ となっている。ここで 2 つの正の整数の組 $i, j$ に対して正の整数 $f(i, j)$ を返す関数 $f$ を考える。

次の条件を満たす操作列を構築せよ。1 つの操作は整数 $1 \le i \lt j \le N$ で与えられ、

$a_{i}$ , $a_{j}$ をともに $f(a_{i}, a_{j})$ で置き換える

というものとなる。この一連の操作を行って得られる数列が、「高々 2 種類の値しかない」という状態になるようにしたい。

どのような関数 $f$ に対してもそれを満たせるような操作列 (長さが $5 \times 10^{5}$ 以下) を構築せよ。

制約

$1 \le N \le 15000$

考えたこと

$N$ の値によっては、「すべての整数が同じ値」という風にはできないようだ。

$N = 2$ であれば、操作 (1, 2) を行うことですべて同じにできる
$N = 4$ であれば、操作 (1, 2), (3, 4), (1, 3), (2, 4) を行うことですべて同じにできる
$N = 8$ であれば、前半 (1, 2, 3, 4) と後半 (5, 6, 7, 8) をすべて同じにした上で、(1, 5), (2, 6), (3, 7), (4, 8) を行うことですべて同じにできる

$N = 3$ のときはどうしても無理になる。でも、どうやら $N = 2^{K}$ と表せるときはすべて同じにできるようだ。具体的には次のようにすればよい。

前半 $2^{K-1}$ 個と、後半 $2^{K-1}$ 個をそれぞれ揃える
前半の $i$ 個目と、後半の $i$ 個目をそろえることを $i = 1, 2, \dots, 2^{K-1}$ に対して行う

一般の N では

一般の $N$ ではおそらく「すべてを同じ」にできるとは限らない。しかし、

$2^{K} \lt N \le 2^{K+1}$

を満たすような $K$ をとったとき

左から $2^{K}$ 個を揃える (2 の冪乗個はすべて一致させられる)
右から $2^{K}$ 個を揃える

という 2 ステップの操作によって、「2 種類の値」となるようにできる。なぜなら

$2^{K} + 2^{K} = 2^{K+1} \ge N$

なので、

左から $N - 2^{K}$ 個が等しい
右から $2^{K}$ 個が等しい

という状態にできる。

見積り

念のために、上記の操作回数を見積もっておきたい。とくに $N = 2^{K}$ と表せるときの操作回数を見積もっておく。これを $a_{K}$ とおくと、

$a_{0} = 0$
$a_{K+1} = 2a_{K} + 2^{K}$

という漸化式が成立する。よって、 $b_{K} = \frac{a_{K}}{2^{K}}$ とおくと、

$b_{K+1} = b_{K} + \frac{1}{2}$

となるので

$a_{K} = 2^{K} b_{K} = 2^{K} \times \frac{K}{2} = K 2^{K-1}$

が成立する。つまりざっくり、 $O(N \log N)$ 回の操作回数ということになる。十分足りる。

コード

#include <bits/stdc++.h>
using namespace std;

using pint = pair<int,int>;
void rec(int left, int right, vector<pint> &res) {
    if (right - left <= 1) return;
    int mid = (left + right) / 2;
    rec(left, mid, res), rec(mid, right, res);
    for (int i = left, j = right - 1; i < j; ++i, --j)
        res.emplace_back(i, j);
}

int main() {
    int N, K = 0;
    cin >> N;
    while (N > (1<<(K+1))) ++K;
    vector<pint> res;
    rec(0, (1<<K), res);
    rec(N-(1<<K), N, res);
    cout << res.size() << endl;
    for (auto p : res) cout << p.first+1 << " " << p.second+1 << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Grakn Forces 2020 F. Two Different (R2300)

問題概要

制約

考えたこと

一般の N では

見積り

コード