selpo's diary

主に競プロの解説をします。C#erです。

問題C『N!÷K番目の単語』 : ARC(AtCoder Regular Contest) 047

問題文 : N!÷K番目の単語

概要

1,2,\ldots,Nの並び替え(N! 個ある)を辞書順に並べたとき、
1-indexedでN!/K番目にくる並び替えは何か。

制約

1\leq K\leq N\leq 10^5

解説

並び替えといえば階乗進数。
0-indexedでN!/K-1番目の数に対応する階乗進数表記が求まればよい。
階乗進数と順列の対応付け - 猫尾製作所
とりあえず、階乗進数と並び替えの関係について説明する。

階乗進数

上のリンク先にもあるが、少し詳しく解説しておく。
0,1,\ldots,N-1の並び替えのほうが分かりやすいので、以下ではそうする。
また、以下0-indexedで考える。

(1)並び替えから番号を求める

例えば351402という並び替えがあったら、これは012345の並び替えのうち、
3\cdot 5!+4\cdot 4!+1\cdot 3!+2\cdot 2!+0\cdot 1!=466番目になる。

数え方は、受験数学でもたまに出るが、以下の通り、
351402は301245を基準にして数える。
301245は0*****、1*****、2*****の次に来るので3\cdot 5!番目。
51402は50124を基準にして数える。
50124は0****、1****、2****、3****、4****の次に来るので5\cdot 4!番目。
以下同様にやると、上の式になる。

アルゴリズムを考えてみよう。集合を表すデータ構造が必要で、必要な操作は、

  1. ある数が残った数のうち何番目に大きいか
  2. ある数を削除

である。これは、BIT(Fenwick Tree)を用意すれば、以下のようにO(N\log N)でできる。

long PermutationToNumber(int[] x)
{
	var N = x.Length;
	var bit = new BIT(N);
	for (var i = 0; i < N; i++) bit.Add(i, 1); // i 番目に 1 を足す
	var ans = 0L;
	for (var i = 0; i < N; i++)
	{
		// bit.Sum = (x[i] 未満の数がいくつ残っているか) = (x[i] が何番目か)
		ans += Fact(N - i - 1) * bit.Sum(0, x[i]);
		bit.Add(x[i], -1); // x[i] を削除
	}
	return ans;
}

ちなみに、並び替えから直接階乗進数を求めるのも、これをちょっと書き換える(ansをfactorial[N - i - 1]とする)だけでできる。

(2)階乗進数

上で出てきた式がまさに階乗進数である。

正確に言うと、ある自然数nの階乗進数表記とは、(m-1)!\leq n\leq m!を満たす自然数mおよび
適当な非負整数列0\leq a_i\leq i\,\,(0\leq i\lt m)を用いて、n=\displaystyle\sum_{0\leq i\lt m}a_ii!と表すことである。
この表し方が一意であることは容易にわかる。
これを、n=[a_{m-1},\ldots,a_1,a_0]と記し、mを長さと呼ぶ。
また、[2,3,0,1,0]=[0,0,2,3,0,1,0]のように余分な0を含めて書くことも許す(10進数で2301を002301と書くのと同じ)。
この場合、付け加えた0も含めて、長さを数えることにする。

そうすると、0,1,\ldots,N-1の並び替えと、長さNの階乗進数が対応することがわかる。
(常にa_0=0であるので省略してもよいが、含めておくと場合分けが減ってすっきりするので、含めることが多い。)

(3)番号から階乗進数を求める

階乗進数から番号を求めるのは\displaystyle\sum_{0\leq i\lt m}a_ii!でよい。
階乗を計算しないよう工夫すると、以下の通り。

long FactToNumber(int[] fact)
{
	var m = fact.Length;
	var ans = 0L;
	for (var i = m - 1; i >= 0; i--)
		ans = (i + 1) * ans + fact[i];
	return ans;
}

逆はどうするか?

まず、nに対し、(m-1)!\leq n\leq m!を満たす自然数mを求める。
そして、a_{m-1}=\lfloor n/(m-1)!\rfloorおよびn\leftarrow \bmod(n,(m-1)!)とする。
以下、順にa_{i}=\lfloor n/i!\rfloorおよびn\leftarrow \bmod(n,i!)とする(i=m-2,\ldots,2,1の順にやる)。
やはり階乗を使わずにできる。

int[] NumberToFact(long n)
{
	var fact = new List<int>();
	for (var i = 1; n > 0; i++)
	{
		fact.Add((int)(n % i));
		n /= i;
	}
	return fact.ToArray();
}
(4)階乗進数から並び替えを求める

(1)の逆をやる。
つまり、例えばさっきの351402なら、466=[3,4,1,2,0,0]だったが、逆に階乗進数から並び替えの復元を考える。
並び替えがx_0x_1x_2x_3x_4x_5であるとする。

並び替えには012345が使えて、a_5=3なので、x_0は3番目の数で、x_0=3
残った数は01245で、a_4=4なので、x_1は4番目の数で、x_1=5
残った数は0124で、a_3=1なので、x_2は1番目の数で、x_2=1
残った数は024で、a_2=2なので、x_3は2番目の数で、x_3=4
残った数は02で、a_1=0なので、x_4は0番目の数で、x_4=0
残った数は2で、a_0=0なので、x_5は0番目の数で、x_5=2

一般化は容易に想像できるだろう。
以上を実現するために必要なデータ構造は、

  1. ある数を削除
  2. 残った数のうちa番目のものを取得

が高速にできればよく、やはりBIT(Fenwick Tree)でできる。
2番目はBIT上で二分探索すればよい。
つまり、[0,x)までにいくつ残っているかがBITのSumによって分かるので、xについて二分探索。

int[] FactToPermutation(int[] fact)
{
	var N = fact.Length;
	var bit = new BIT(N);
	for (var i = 0; i < N; i++) bit.Add(i, 1); // 0,1,...,N-1 を 1 個ずつ用意
	var x = new int[N];
	for (var i = 0; i < N; i++)
	{
		// x[i] = (bit.Sum(0,t) >= fact[N-i-1]+1 を満たす最小の t)
		// つまり、残った数のうち0-indexedで fact[N-i-1] 番目の数
		x[i] = FirstBinary(0, N, t => bit.Sum(0, t + 1) >= fact[N - i - 1] + 1);
		bit.Add(x[i], -1); // x[i] を削除
	}
	return x;
}

解説(続き)

ここまでくればあとは簡単。
N!/K-1を長さNの階乗進数のまま計算しておけば、さっきの FactorialToPermutationによって答えが求まる。
要は(4)しか使わない。

まず、N!を表すために、いったん長さをN+1にしておく。
すると、N!=[1,0,\ldots,0]が容易にわかる。
そして、N!/Kは、筆算の要領で以下のように求まる(ちなみに、K\leq Nだから、必ず割り切れる)。

var fact = new List<int>();
for (var i = 0; i < N; i++) fact.Add(0);
fact.Add(1); // この時点で、fact=[1,0,...,0]=N!
var r = 0L; // 余り
for (var i = N; i > 0; i--)
{
	var y = fact[i] + r * (i + 1);
	fact[i] = (int)(y / K);
	r = y % K;
}
fact.RemoveAt(N);

少し解説すると、以下のような感じ。

まず、階乗進数の性質から、少し記法を拡張すれば(a_i\gt iを許せば)、
[1,0,0,0,0,0,0]=6!=6\cdot 5!=[0,6,0,0,0,0,0]=[0,0,30,0,0,0,0]
などとなる。ゆえに、
[1,0,0,0,0,0,0]/4=[0,6,0,0,0,0,0]/4=[0,1,0,0,0,0,0]+[0,2,0,0,0,0,0]/4
[0,2,0,0,0,0,0]/4=[0,0,10,0,0,0,0]/4=[0,0,2,0,0,0,0]+[0,0,2,0,0,0,0]/4
[0,0,2,0,0,0,0]/4=[0,0,0,8,0,0,0]/4=[0,0,0,2,0,0,0]
よって、6!/4=[1,0,0,0,0,0,0]/4=[0,1,2,2,0,0,0]となる。
一般化すると、上のコードになる。
あるいは、初めからN!=[N,0,\ldots,0]としておけば、以下のようになる。

var fact = new int[N];
fact[N - 1] = N;
var r = 0L;
for (var i = N - 1; i >= 0; i--)
{
	var y = fact[i] + r * (i + 1);
	fact[i] = (int)(y / K);
	r = y % K;
}

次に、階乗進数から1を引くという操作をしたい。
初めて0でなくなる添え字を見つけて、そこから借りてくればいい。
つまり、M!-1=\sum_{0\leq i\lt M}i\cdot i!だから、例えば
2\cdot 7!+5\cdot 6!+4\cdot 5!-1=2\cdot 7!+5\cdot 6!+3\cdot 5!+(4\cdot 4!+3\cdot 3!+2\cdot 2!+1\cdot 1!)なので、
[2,5,4,0,0,0,0,0]-1=[2,5,3,1,1,1,1,0]のようになる。

ソースコード

ほとんど上で説明しきっているので、必要ないといえばないが、一応貼っておく。

using System;
using System.IO;
using System.Linq;
class E
{
	static int[] G() { return Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray(); }
	static void Main()
	{
		Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
		var I = G();
		int N = I[0], K = I[1];
		var fact = new int[N];
		fact[N - 1] = N;
		var r = 0L;
		for (var i = N - 1; i >= 0; i--)
		{
			var y = fact[i] + r * (i + 1);
			fact[i] = (int)(y / K);
			r = y % K;
		}
		var j = 0;
		while (fact[j] == 0) j++;
		fact[j]--;
		for (var i = j - 1; i > 0; i--) fact[i] = i;
		var x = FactorialToPermutation(fact);
		for (var i = 0; i < N; i++) Console.WriteLine(x[i] + 1);
		Console.Out.Flush();
	}
	static int[] FactorialToPermutation(int[] fact)
	{
		var N = fact.Length;
		var bit = new BIT(N);
		for (var i = 0; i < N; i++) bit.Add(i, 1);
		var x = new int[N];
		for (var i = 0; i < N; i++)
		{
			x[i] = FirstBinary(0, N, t => bit.Sum(0, t + 1) >= fact[N - i - 1] + 1);
			bit.Add(x[i], -1);
		}
		return x;
	}
	static int FirstBinary(int min, int max, Predicate<int> pred)
	{
		var left = min;
		var right = max;
		while (left < right)
		{
			var mid = (left + right) >> 1;
			if (pred(mid)) right = mid;
			else left = mid + 1;
		}
		return left;
	}
}
class BIT
{
	int size;
	int[] bit;
	public BIT(int size) { this.size = size; bit = new int[size + 1]; }
	public void Add(int index, int value) { for (var i = index + 1; i <= size; i += i & (-i)) bit[i] += value; }
	public int Sum(int from, int to) { return Sum(to) - Sum(from); }
	int Sum(int to) { var sum = 0; for (var i = to; i > 0; i -= i & (-i)) sum += bit[i]; return sum; }
}

感想

知ってればわりと簡単。
並び替えと階乗進数を相互に変換するのは、普通にListでやるとO(N^2)かかってしまうが、
BIT(Fenwick Tree)を用いればN\log Nでできる、というのがミソ。
今回の[0,N)のように、範囲が決まっていればBITを用いて集合を表すことができる、というのが重要。

階乗進数の計算は、足し算、引き算、掛け算、割り算のいずれも、筆算の要領でできるので、もっと複雑になっても対応できる。