日々drdrする人のメモ

今日もdrdr、明日もdrdr

ARC047 - C問題: N!÷K番目の単語

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

問題: 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)のインデックスであるため、辞書順において1つ前のインデックスを計算する必要があるが、デクリメント的に計算できる。


今回書いたコード。計算量は {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')

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