完全n分木とn進数

June 23, 2020

AtCoder ABC 171 Cを時間内に解きはしたけど、コンテスト中はあまり考えが整理されておらず、感覚的に解いてしまった。解説では、26進数として見て、N番目の文字列が何かを答えるとしていた。個人的には、完全n分木のN番目のノードの文字列が何かを考えるほうがわかりやすくて好きなので、メモっておく。本質的にはどちらもやっていることは同じ。

完全n分木

完全n分木における、ノードへの番号の振り分け方は、根から葉へ、同じ深さでは左から右に大きくなるように番号を振り分ける。たとえば、完全二分木では、根に0、その子ノードは左から1,2、1の子ノードは3,4というように番合を振る。

親ノードと子ノードの番号の関係

完全n分木(n = 2, 3)とかを適当に書いてみると、親ノードと子ノードの番号が満たす性質に気づく。

番号 $C_i$ をもつ、あるノードに着目しているとする。そのノードは自身の親ノード( $P$ )の子ノードで、左から数えてi(= 0,1,2,…)番目にある。

$\begin{eqnarray*} C_i &=& P * n + i + 1 \\ P &=& \lfloor (C_i - 1) / n \rfloor \end{eqnarray*}$

この性質については、地道に計算すれば証明できる。

ABC 171 C

根を空白文字として考えて、与えられた番号を持つノードから根へのパスを辿って答えとなる文字列を作ればいい。

実装

#define N_ALPHABET 26

int main() {
    i64 N; cin >> N;

    string ans = "";
    while (N > 0) {
        i64 parent = (N - 1) / N_ALPHABET;
        i64 ci = N - (parent * 26 + 1);
        ans += ('a' + ci);
        N = parent;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;

    return 0;
}