ならば
になるネタ、結構見る!
問題概要
数列 があって、初期状態では
となっている。ここで 2 つの正の整数の組
に対して正の整数
を返す関数
を考える。
次の条件を満たす操作列を構築せよ。1 つの操作は整数 で与えられ、
,
をともに
で置き換える
というものとなる。この一連の操作を行って得られる数列が、「高々 2 種類の値しかない」という状態になるようにしたい。
どのような関数 に対してもそれを満たせるような操作列 (長さが
以下) を構築せよ。
制約
考えたこと
の値によっては、「すべての整数が同じ値」という風にはできないようだ。
であれば、操作 (1, 2) を行うことですべて同じにできる
であれば、操作 (1, 2), (3, 4), (1, 3), (2, 4) を行うことですべて同じにできる
であれば、前半 (1, 2, 3, 4) と後半 (5, 6, 7, 8) をすべて同じにした上で、(1, 5), (2, 6), (3, 7), (4, 8) を行うことですべて同じにできる
のときはどうしても無理になる。でも、どうやら
と表せるときはすべて同じにできるようだ。具体的には次のようにすればよい。
- 前半
個と、後半
個をそれぞれ揃える
- 前半の
個目と、後半の
個目をそろえることを
に対して行う
一般の N では
一般の ではおそらく「すべてを同じ」にできるとは限らない。しかし、
を満たすような をとったとき
- 左から
個を揃える (2 の冪乗個はすべて一致させられる)
- 右から
個を揃える
という 2 ステップの操作によって、「2 種類の値」となるようにできる。なぜなら
なので、
- 左から
個が等しい
- 右から
個が等しい
という状態にできる。
見積り
念のために、上記の操作回数を見積もっておきたい。とくに と表せるときの操作回数を見積もっておく。これを
とおくと、
という漸化式が成立する。よって、 とおくと、
となるので
が成立する。つまりざっくり、 回の操作回数ということになる。十分足りる。
コード
#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; }