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

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

Codeforces Grakn Forces 2020 F. Two Different (R2300)

 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} \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;
}