問題C『N!÷K番目の単語』 : ARC(AtCoder Regular Contest) 047
問題文 : N!÷K番目の単語
概要
の並び替え( 個ある)を辞書順に並べたとき、
1-indexedで番目にくる並び替えは何か。
制約
解説
並び替えといえば階乗進数。
0-indexedで番目の数に対応する階乗進数表記が求まればよい。
階乗進数と順列の対応付け - 猫尾製作所
とりあえず、階乗進数と並び替えの関係について説明する。
階乗進数
上のリンク先にもあるが、少し詳しく解説しておく。
の並び替えのほうが分かりやすいので、以下ではそうする。
また、以下0-indexedで考える。
(1)並び替えから番号を求める
例えば351402という並び替えがあったら、これは012345の並び替えのうち、
番目になる。
数え方は、受験数学でもたまに出るが、以下の通り、
351402は301245を基準にして数える。
301245は0*****、1*****、2*****の次に来るので番目。
51402は50124を基準にして数える。
50124は0****、1****、2****、3****、4****の次に来るので番目。
以下同様にやると、上の式になる。
アルゴリズムを考えてみよう。集合を表すデータ構造が必要で、必要な操作は、
- ある数が残った数のうち何番目に大きいか
- ある数を削除
である。これは、BIT(Fenwick Tree)を用意すれば、以下のようにでできる。
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)階乗進数
上で出てきた式がまさに階乗進数である。
正確に言うと、ある自然数の階乗進数表記とは、を満たす自然数および
適当な非負整数列を用いて、と表すことである。
この表し方が一意であることは容易にわかる。
これを、と記し、を長さと呼ぶ。
また、のように余分な0を含めて書くことも許す(10進数で2301を002301と書くのと同じ)。
この場合、付け加えた0も含めて、長さを数えることにする。
そうすると、の並び替えと、長さの階乗進数が対応することがわかる。
(常にであるので省略してもよいが、含めておくと場合分けが減ってすっきりするので、含めることが多い。)
(3)番号から階乗進数を求める
階乗進数から番号を求めるのはでよい。
階乗を計算しないよう工夫すると、以下の通り。
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; }
逆はどうするか?
まず、に対し、を満たす自然数を求める。
そして、およびとする。
以下、順におよびとする(の順にやる)。
やはり階乗を使わずにできる。
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なら、だったが、逆に階乗進数から並び替えの復元を考える。
並び替えがであるとする。
並び替えには012345が使えて、なので、は3番目の数で、。
残った数は01245で、なので、は4番目の数で、。
残った数は0124で、なので、は1番目の数で、。
残った数は024で、なので、は2番目の数で、。
残った数は02で、なので、は0番目の数で、。
残った数は2で、なので、は0番目の数で、。
一般化は容易に想像できるだろう。
以上を実現するために必要なデータ構造は、
- ある数を削除
- 残った数のうち番目のものを取得
が高速にできればよく、やはりBIT(Fenwick Tree)でできる。
2番目はBIT上で二分探索すればよい。
つまり、までにいくつ残っているかがBITのSumによって分かるので、について二分探索。
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; }
解説(続き)
ここまでくればあとは簡単。
を長さの階乗進数のまま計算しておけば、さっきの FactorialToPermutationによって答えが求まる。
要は(4)しか使わない。
まず、を表すために、いったん長さをにしておく。
すると、が容易にわかる。
そして、は、筆算の要領で以下のように求まる(ちなみに、だから、必ず割り切れる)。
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);
少し解説すると、以下のような感じ。
まず、階乗進数の性質から、少し記法を拡張すれば(を許せば)、
などとなる。ゆえに、
よって、となる。
一般化すると、上のコードになる。
あるいは、初めからとしておけば、以下のようになる。
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でなくなる添え字を見つけて、そこから借りてくればいい。
つまり、だから、例えば
なので、
のようになる。
ソースコード
ほとんど上で説明しきっているので、必要ないといえばないが、一応貼っておく。
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でやるとかかってしまうが、
BIT(Fenwick Tree)を用いればでできる、というのがミソ。
今回ののように、範囲が決まっていればBITを用いて集合を表すことができる、というのが重要。
階乗進数の計算は、足し算、引き算、掛け算、割り算のいずれも、筆算の要領でできるので、もっと複雑になっても対応できる。