解説AC
テキストとyoutubeの解説の自分用まとめです。特に新しいことはありません。公式を見た方が詳細です。
二分木として考える
各文字が2つの文字になることを順に図示すると、二分木の構成になります。
よって、この問題は、
を根とする二分木における、深さ
で
番目の文字を求めよ
という問題と見ることができます。
における0,1,2をA,B,Cに対応させます。
Aの左子ノードがB、右子ノードがCであるとします。
左子ノードに進むことは、において+1すること、右子ノードに降りることは+2することと同じです。B,Cにおいても同様に考えることができます。
よって、親の文字がわかれば子の文字を求めることができます。
以降、+xするという表現は上での操作を指します。
親と子の番号の関係
深さにおいて、
番目である場合、その子は、深さ
において、左子ノードが
番目、右子ノードが
となります。
以下が理由です。
深さにおいて
番目である場合、自分より前には
までの
個のノードが存在する。
深さには、それらの子ノードが2個ずつ存在し、その数は
個となる。それらの番号は、
となるから。
これより、
- 親が
番目なら、子の番号は左が
、右が
- 子の番号が
なら親の番号は、
が言えます。
また、
- 子の番号が偶数なら親の左子ノード、奇数なら右子ノード
も言えます。
が小さい場合
解説にならって、の
番目の文字を求める関数を
とおきます。
以下のように再帰的に求められます。
を求め、
が偶数なら+1、奇数なら+2します。
が十分小さい場合、再帰の過程で
となります。この時、
を
として返せばよいです。
が大きい場合
深さが1増えると子の数は2倍になります。
深さから、60回深いところに進むと、
番目の文字は全て
の子孫であることがわかります。
の最大値は
であることから、
から60回ほど親を遡ったところを
とすれば、深さ
の
番目の文字は全て
の子孫となります。
ある深さにおける
は、全て
の左子ノードを
回進んだ文字であるので、
することで求められます。
以上より、再帰においてを1/2していくと、高々60回ほどで、
となります。このとき、
を
として返すようにすればよいです。
提出コード(公式とほぼ同じ)