ARC047 - C問題: N!÷K番目の単語 - 日々ｄｒｄｒする人のメモ

自分のための解法メモ (公式の解法スライド読んでピンとこなかったので)

今回は、 ${i}$ 番目 ${(i = 1, 2, \ldots, N)}$ の数字において、その時点で残っている数字のうち、小さい方から何番目の数字を使うかを表すインデックス(0-indexed)を計算する。

1つ目の数字のインデックスは ${\frac{N!}{K} = (N-1)!m_1 + q_1}$ における ${m_1}$ である。
( ${m_1, q_1}$ は整数で、 ${0 \le q_1 < (N-1)!}$ )
それぞれの値を計算すると、以下のようになる。 ( ${A \% B}$ はAをBで割ったあまりとする)
${q_1 = \frac{(N-1)!}{K}(N - Km_1) = \frac{(N-1)!}{K}(N \% K)}$
${m_1 = \lfloor \frac{N}{K} \rfloor}$
ここで、 ${A_1 = N \% K}$ とすると、 ${q_1 = \frac{(N-1)!}{K}A_1}$ と表せる。

次に、2つ目の数字(のインデックス)は ${q_1}$ の値を利用し計算できる。
${q_1 = (N-2)!m_2 + q_2}$ の ${m_2}$ として計算できる。( ${m_2, q_2}$ は整数で、 ${0 \le q_2 < (N-2)!}$ )
各値を計算すると以下のようになる。
${q_2 = \frac{(N-2)!}{K}( (N-1)A_1 - Km_2) = \frac{(N-2)!}{K}( ( (N-1)A_1) \% K)}$
${m_2 = \lfloor \frac{(N-1)A_1}{K} \rfloor}$
このとき、 ${A_2 = ( (N-1)A_1) \% K}$ とすると、 ${q_2 = \frac{(N-2)!}{K}A_2}$ と表せる。

同様に計算していくと、 ${i}$ 番目のインデックス ${(i = 1,2,\dots,N)}$ は以下のように表せることが分かる。
${q_i = \frac{(N-i)!}{K}A_i}$
${A_0 = 1, A_i = ( (N-(i-1))A_{i-1}) \% K}$
${m_i = \lfloor \frac{(N-(i-1))A_{i-1}}{K} \rfloor}$

ここで解のために必要となる値は ${m_i (i = 1,2,\dots,N)}$ であり、大きい値になる ${q_i}$ を計算せずに ${A_i (\le K)}$ を計算するだけで済むのがポイント。

今回必要となるBIT上のlower boundは1回 ${O(\log{N})}$ で計算できる。
以下が参考になった。
http://hos.ac/slides/20140319_bit.pdf

あと、ここで計算できるのは辞書順で ${\frac{N!}{K}+1}$ 番目 (0-indexed)のインデックスであるため、辞書順において１つ前のインデックスを計算する必要があるが、デクリメント的に計算できる。

今回書いたコード。計算量は ${O(N \log{N})}$ 。
Submission #2099468 - AtCoder Regular Contest 047

N, K = map(int, input().split())

# BIT
data = [0]*(N+1)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k

# BIT上のlower bound
def lower_bound(w):
    i = 0; s = 0
    k = 2**(N.bit_length()-1)
    while k > 0:
        if i + k <= N and data[i + k] < w:
            w -= data[i + k]
            i += k
        k >>= 1
    return i+1
 
# 各インデックスを計算
a = 1
res = []
for i in range(N):
    m = (N-i)*a // K
    res.append(m)
    a = ((N-i)*a) % K
    add(i+1, 1)

# 計算したのはN!/K (0-indexed)であるため、インデックスを1戻す
idx = N-1
while res[idx] == 0:
    res[idx] = N-1-idx
    idx -= 1
res[idx] -= 1
 
# 各インデックスに対応する数字をBITから求める
ans = []
for i in res:
    idx = lower_bound(i+1)
    add(idx, -1)
    ans.append(idx)
print(*ans, sep='\n')

こういうシンプルな問題、手の付け方が難しい。