AtCoder Regular Contest 047 C - N!÷K番目の単語

問題

　までの整数による順列は個あるが、それらを辞書順に並べたときの個目のものを求めよ。

解法

　先頭からどの数字を置くべきか決定していくが、それを「まだ使っていない数字の中で何番目に小さいものを置くべきか」を求めることによって決定していく。辞書順番目のものについて、たとえば1文字目は数字を決めると2番目以降は通りあるためを置けば良い。

　ここでであるから、これをで割った商はの商に等しく、余りはであるという性質がある。これにより2文字目を決定するときは余りの数を用いてと求められる。何を言っているのか理解できていないので解説スライドを参照のこと。

反省

　2時間54分(1WA)でAC。睡眠不足と体調不良でほとんどまともに考察できなかったが、とりあえず2時間を過ぎたあたりで解説スライドを見た。しかし何を言っているのか理解ができず、他の人の提出を見てほぼ写して通したという感じになった。最初の部分もわからないし、それを求めたあともBITを使って二分探索すればいいというのも出てこない考えだと思う。

　0-indexedによるズレが生じるのも面倒で、prev_permutationを使って戻す実装にしてみたところ、でWAが出るようだ。確かに手元でやってみるとそうなるんだけどさっぱりわからない。そこだけ場合分けしたらなんとか通った(これも他の人の提出で場合分けされていたのでやってみただけ)が、謎である。とにかく難しい問題だった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class BinaryIndexedTree {
public:
    BinaryIndexedTree(ll N) : N_(N), bit_(N + 1, 0) {}
    void add(ll a, ll w) {
        for (ll x = a; x <= N_; x += (x & -x)) {
            bit_[x] += w;
        }
    }
    ll sum(ll a) {
        ll result = 0;
        for (ll x = a; x > 0; x -= (x & -x)) {
            result += bit_[x];
        }
        return result;
    }
private:
    ll N_;
    vector<ll> bit_;
};

int main() {
    ll N, K;
    cin >> N >> K;

    if (K == 1) {
        for (ll i = N; i >= 1; i--) {
            cout << i << endl;
        }
        return 0;
    }

    //残っているものの中で何番目か
    vector<ll> f(N);

    //解説スライドにおける「整数」
    ll p = 1;

    //先頭から決定していく
    for (ll i = 0; i < N; i++) {
        f[i] = (N - i) * p / K + 1;
        p = (N - i) * p % K;
    }

    BinaryIndexedTree bit(N);
    for (ll i = 1; i <= N; i++) {
        bit.add(i, 1);
    }

    vector<ll> ans;
    for (ll i = 0; i < N; i++) {
        //bitの値を使って二分探索をする
        //残っているものの中でx番目の数字 <=> bit.sum(j) = xとなるj
        ll low = 0, eq_high = N;
        while (low + 1 != eq_high) {
            ll mid = (low + eq_high) / 2;
            (bit.sum(mid) < f[i] ? low = mid : eq_high = mid);
        }
        ans.push_back(eq_high);
        bit.add(eq_high, -1);
    }

    //求めたのは0-indexedのN!÷K番目なので1個戻す
    prev_permutation(ans.begin(), ans.end());

    for (ll a : ans) {
        cout << a << endl;
    }
}