解説

〔アについて〕
34と78をぞれぞれM/2桁＝1桁ずつに分けてA、B、C、Dの4つの多倍長整数で表現すると、次のようになります。

• A … 3 = {3}
• B … 4 = {4}
• C … 7 = {7}
• D … 8 = {8}

図2のツリー構造を見ると3つの子ノードは、①のノード（左）が「A×C」に、②のノード（中央）が「B×D」に、③のノード（右）が「(A＋B)×(C＋D)」にそれぞれ対応しているので、空欄アは「A×C」が当てはまることがわかります。したがって「3×7」が適切です。

∴ア＝3×7

〔イについて〕
上記と同じく、46と134をA、B、C、Dの4つの多倍長整数で表現していきますが、「(A＋B)，(C＋D) は…"桁ごとの加算"だけを行い，"繰り上がり"の処理はツリーを用いて行う演算の最後でまとめて行う」という説明に注意します。

層1から層2③のノードを作るところから考えると、1234と5678は、

• A … 12 = {2, 1}
• B … 34 = {4, 3}
• C … 56 = {6, 5}
• D … 78 = {8, 7}

というように分割され、桁ごとの加算だけが行われます。

• A＋B = {2＋4, 1＋3} = {6, 4}
• C＋D = {6＋8, 5＋7} = {14, 12} //繰り上がりはない

繰り上がりの処理はしないので、層2③の134は{4, 3, 1}という3桁で保持されているのではなく、{14, 12}という2桁であると考えなければなりません。

これを踏まえて、46と134をM/2桁＝1桁ずつに分けてA、B、C、Dの4つの多倍長整数で表現すると、次のようになります。

• A … 4 = {4}
• B … 6 = {6}
• C … 12 = {12}
• D … 14 = {14}

①のノード（左）は「A×C」となるので、空欄イには「4×12」が当てはまります。

∴イ＝4×12

解説

本文中の式(1)と設問2の式を比較すると、①とα、②とγ、③とα、④とβがそれぞれ対応しています。α・β・γは、それぞれ計算対象ノードの子ノード①・②・③の乗算の計算結果ですから、

• α（子ノード①の計算結果）4×12＝48
• β（子ノード②の計算結果）6×14＝84
• γ（子ノード③の計算結果）10×26＝260

したがって、αに対応する①と③には「48」、βに対応する④には「84」、γに対応する②には「260」が当てはまります。

∴①＝48、②＝260、③＝48、④＝84

解説

解説の便宜上、図3のプログラムに行番号を振っておきます。〔ウについて〕
配列 elements は、ルートノードを先頭に、各層の左側から順にノードを格納した配列です。配列 layer_top は、各層の左端ノードの、配列 elements 上での添字の値を保持する配列ですから、図2の場合、配列 layer_top の各要素には{1, 2, 5}が設定されます。空欄ウを含む部分は、2行目で配列 layer_top の先頭要素に層1の左端であるルートノードを示す1を代入した後、3～5行目のfor文で層2以降の左端ノードを示す添字の値を設定します。上の図を参考にすると層2の左端ノードの添字は2、層3は5、層4は14となります。配列 layer_top への値の代入は、前の要素の値に一定数を加算する形で行われているので、

• i=1 → 1 + 1 = 2
• i=2 → 2 + 3 = 5
• i=3 → 5 + 9 = 14

の赤太字で示した部分が空欄ウに対応し、これをループ変数iと絡めて表現する式が当てはまることになります。

各ノードは3個の子ノードを持つので、層2のノードの個数は「3個」、層3は「3×3＝9個」、層4は「3×3×3＝27個」、…と1層下がるごとに3倍ずつ増えていきますから、層iのノードの数（赤太字の数）は 3^i-1 の式で表すことができます。これを層iの左端ノードの添字に加算すれば、ひとつ下の層の左端ノードの添字となります。累乗は表3の関数 pow(m, k) を用いて記述できるので、答えは「pow(3, i-1)」です。

∴ウ＝pow(3，i－1)

〔エについて〕
ツリーを構築する部分は、ルートノードの層から最下層以外の層まで順に、ノードごと3つの子ノードを作っていく処理です。10～18行目の入れ子になったfor文はそれぞれ次のような繰返しを行います。変数 dp は、現在の層の番号、変数 i は各層上のノードの番号を示しています。
変数 tidx は、コメント部にあるように「子ノード①へのインデックス」、すなわち子ノード①の配列 elements 上の添字ですから、図2において層2から層3を作るときのことを考えると、dp、i および tidx は次のように対応します。ひとつ下の層の左端ノードの位置を保持する layer_top[dp+1] を起点にすると、子ノード①の添字は、

• i=1のとき layer_top[dp+1]（上図では5＋0＝5）
• i=2のとき layer_top[dp+1] + 3（上図では5＋3＝8）
• i=3のとき layer_top[dp+1] + 6（上図では5＋6＝11）

と3つずつずれていきますから、親ノードがi番目の場合、子ノード①の添字は layer_top[dp+1] の値に 3×(i-1) を加算することで求めることができます。 したがって、空欄エには「3*(i-1)」が当てはまります。

∴エ＝3*(i-1)

〔オカについて〕
〔ツリー構造の構築〕の説明を踏まえると、14～16行目は3つの子ノードを作成する処理に当たることがわかります。14行目が子ノード①、15行目が②、16行目が③を作成する処理です。空欄は共通しているので14行目に着目して考えていきます。

子ノードの生成に使われている関数 new_elem の説明より、14行目のnew_elem(cn, left([オ], cn), left([カ], cn))は、「取り扱う多倍長整数の桁数がcnで、left([オ], cn) の値と left([カ], cn) の値の乗算を表すノード」を作成するという意味になります。子ノード①は〔ツリー構造の構築〕でいうところの「A×C」なので、left([オ], cn)はA、left([カ], cn)はCに相当することになります。関数 left(p, k) は「多倍長整数 p の上位 k 桁を返す」関数であり、第2引数に指定されている変数 cn には、12行目で「子ノードの桁数(=親ノードの桁数Mの1/2)」が格納されていますから、第1引数である空欄オ・カには多倍長整数を指定すべきであることがわかります。

〔ツリー構造の構築〕の説明に沿ってAとCを言い換えると、Aは「親ノードの乗算記号の左の値の左半分(上位M/2桁)」、Cは「親ノードの乗算記号の右の値の左半分(上位M/2桁)」と言い表すことができます。左半分の指定は変数 cn によって行われているので、空欄オには「親ノードの乗算記号の左の値」、空欄カには「親ノードの乗算記号の右の値」を示す式を入れればよいことになります。

親ノードは11行目より変数 pe として表現されており、pe には配列 elements 上の要素が代入されています。表3より、配列 elements の型は"ノード"なので、変数 pe の型も"ノード"です。構造体"ノード"について表1で確認すると、構造体"ノード"は要素として乗算記号の左側の値を val1、右側の値を val2 として保持していることがわかります。構造体の要素は「構造体の変数名.要素名」でアクセスするため、親ノードの左側の値は pe.val1、親ノードの右側の値は pe.val2 で参照できます。したがって、空欄オには「pe.val1」、空欄カには「pe.val2」がそれぞれ当てはまります。

なお、乗算記号の左右の値が逆になっても最終的な結果は正しいものとなるので、空欄オに「pe.val2」、空欄カに「pe.val1」を入れても正解となります。

∴オカ＝pe.val1、pe.val2

解説

解説の便宜上、プログラムに行番号を振っておきます。〔キについて〕
2～8行目までのfor文は、最下層のノード（1桁×1桁）ごとに左の値と右の値を乗算し、その結果を構造体"ノード"の result に格納しています。図2に対応させると、以下のような処理が行われることになります。for文では、現在処理中のノードを変数 el に格納した後、el の val1.value[1] と val2.value[1] の乗算結果を変数 mul に代入しています。val1.value[1] は左の値の1の位、val2.value[1] は右の値の1の位に相当します。その後、6行目で result の1の位、7行目で10の位（繰り上がりなし）を求め、それぞれ value[1]、value[2] に代入しています。

左の値と右の値の乗算結果は、変数 mul に格納されているので、その1の位を求めるには、mul を10で割った余りを計算することになります。表3には、剰余を求める関数 mod(m, k) が定義されていますから、これを使用して「mod(mul, 10)」とすれば、1の位を求めることができます。

∴キ＝mod(mul, 10)

〔クケについて〕
2～8行目までのfor文は、最下層以外の層について子ノード①②③の計算結果を使って、〔ツリーを用いた演算〕(1)の式で計算する部分です。15～20行目の一連の処理が下記の式の計算に対応しています。16行目のコメントに「γ－α－βを計算」とある点、多倍長整数同士の減算を行う関数 sub が使われていて、上の式中で減算を行うのは γ－α－β の部分しかないことから、15～16行目は「γ－α－β」を計算する処理であると当たりを付けることができます。関数 sub が2回記述されているので、15行目が「γ－α」に対応し、16行目は「γ－α」の結果（変数 s1）からβを減算していることになります。

前述のように、αは子ノード①、βは子ノード②、γは子ノード③の計算結果を表します。現在処理中のノードの、子ノード①の配列 elements 上の添字は、変数 cidx に格納されているので、cidx を基点にして、子ノード①は elements[cidx]、子ノード②は elements[cidx+1]、子ノード③は elements[cidx+2] で参照することができます。

15行目で行いたい処理は「γ－α」なので、空欄クには子ノード③を参照する elements[cidx+2] が、空欄ケには子ノード①を参照する elements[cidx] が当てはまります。

∴ク＝elements[cidx＋2]
　ケ＝elements[cidx]

解説

配列 values は、多倍長整数を整数の1次元配列として表現したものです。配列の各要素で各桁の値を保持しているので、多倍長整数の桁数と同じだけの要素数が必要となります。

図4の最終行でルートノードの乗算結果を繰り上がり処理することにより、多倍長整数の桁数は、通常の10進数で表した整数の桁数と等しくなります。N桁の最大数同士で乗算した場合、N=1では「9×9＝81」、N=2では「99×99＝9801」、…というように、桁数はNの2倍になります。したがって、N桁同士の計算において配列 values に必要な最大の要素数もNの2倍です。したがって答えは「2×N」となります。

∴2×N