Codeforces Round #309 (Div. 1) B. Kyoya and Permutation

個人的にはかなり新鮮で面白かったです。

問題

Problem - B - Codeforces

解法

まず条件を満たすような数列における特徴に注目します。まず条件を満たすためにはcyclic representationsはすべて長さが2以下でなければなりません。これは割と直感的に明らかで,cyclic representationの中に長さが3以上のものがあったとすると,それが元通りになるためには
[k, k-1, k-2, ..., k-p](kがk-p番目に存在する)のようにcyclic representationが構成されていなければなりません。しかし,この数列はcyclic representationになっていないのでおかしいです。

このことを考慮すると,(一般的に書くのは難しいですが)以下のような感じで書けるはずです(長さが2でcyclicになっているところは[]で囲うことにする)。

長さ5の場合,

1, [3, 2], 4, 5
[2, 1], [4, 3], 5
1, [3, 2], [5, 4]

サンプルを見ると一番最初のような例はすぐ気がつくと思いますが2,3番目のようなものもあることに注意が必要です。

これで一応規則性はわかったのですがこれだけわかってもk番目の数列がどうなるかよくわかりません。なのでとりあえず「長さnの数列は何通りあるのか」ということを考えてみることにします。

とりあえず書き下してみると,
長さ1 1通り
長さ2 2通り
長さ3 3通り
長さ4 5通り
長さ5 8通り
となります。…フィボナッチ数列ですね。なぜこうなるのかを考えてみます。

長さnの数列を考えます(n >= 2とする)。問題の性質から,最初の数は
1, ...
となるか
[2, 1], ...
となるかのいずれかしかありません。上の場合に数列が何通りになるかを考えてみると,残りの数が2, 3, ..., nであり,これはそれぞれの数から1を引くと結局1, 2, ..., n-1を並べる方法は何通りになるのか,という問題と同じになります。

よって,長さnの数列における条件を満たす場合の数をp[n]とすると,最初が1になるような場合の数はp[n-1]です。

最初の2つの数が[2, 1]の場合も同様に考えることにより,p[n] = p[n-1] + p[n-2]とわかるので,これは晴れてフィボナッチ数列であることがわかりました。

今度はこれを上手く使ってk番目の数列を再帰関数を用いて記述する方法を考えます。

上で考えたことを用いると,結局最初が1のものはp[n-1]通りあり,これは辞書順的に考えると最初が[2, 1]のものより先に来ます。よって,数列の長さがnの時点で求めるべき数列が小さい順でp[n-1]以下だったら最初の数は1で確定です。逆に数列が小さい順でp[n-1]より大きかったら最初の2つの数は[2, 1]で確定します。これを再帰関数で記述することにより,k番目の数列を再現することが出来ます。

const int MAXN = 55;
const ll INF = 1ll<<62;
ll fibo[MAXN];
int n;

void dfs(int cur, ll rest) {
    if (cur >= n) {
        cout << endl;
        return;
    }
    //cout << "now cur is " << cur << "  " << rest << endl;
    if (rest <= fibo[n-cur-1]) {
        cout << cur+1 << " ";
        dfs(cur+1, rest);
    } else {
        cout << cur+2 << " " << cur+1 << " ";
        dfs(cur+2, rest-fibo[n-cur-1]);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll k;
    cin >> n >> k;
    fibo[0] = fibo[1] = 1, fibo[2] = 2;
    for (int i = 3; i < MAXN; i++) {
        fibo[i] = fibo[i-1]+fibo[i-2];
        if (fibo[i] >= 1e18) fibo[i] = INF;
    }
    assert(k <= fibo[n]);
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    } else if (n == 2) {
        if (k == 1) cout << "1 2" << endl;
        else cout << "2 1" << endl;
        return 0;
    }
    dfs(0, k);
    return 0;
}