応用情報技術者 2023年 春期 午後 問03

解答の論理構成

1. 図2の層2のノード「34×78（B×D）」を分割
   【問題文】では、子ノード生成の手順を
   「①A×C、②B×D、③(A＋B)×(C＋D) の 3 個の子ノードを作り…」
   と示しています。また分割は “M/2 桁” 単位で行い、桁ごとの加算では繰り上がりをしません。
   • 34 の values 配列は {4, 3}、左 1 桁が 3、右 1 桁が 4。
     → A＝3、B＝4
   • 78 の values 配列は {8, 7}、左 1 桁が 7、右 1 桁が 8。
     → C＝7、D＝8
     よって子ノード①は 3×7、②は 4×8、③は (3＋4)×(7＋8) となります。
     図中で②・③は既に表示されているので、空欄 ア には①の 3×7 が入ります。
2. 図2の層2のノード「46×134（((A＋B)×(C＋D))）」を分割
   • 46 の values 配列は {6, 4}、左 1 桁が 4、右 1 桁が 6。
     → A＝4、B＝6
   • 134 は “繰り上がり前” の結果なので values 配列は {14, 12}
     （1 の位が 14, 10 の位が 12 で桁数は 2 のまま）。
     → C＝12、D＝14
     子ノード①は 4×12、②は 6×14、③は (4＋6)×(12＋14)＝10×26 です。
     図中で②・③は表示済みのため、空欄 イ には①の 4×12 が入ります。
3. 以上より
   ア：3×7
   イ：4×12

誤りやすいポイント

• “桁ごとの加算”後に繰り上がりをしないため、134 のように 2 桁のまま値が 10 以上になるケースを見落としやすいです。
• values 配列は下位桁が添字 1 である点を忘れ、left(p, 1) と right(p, 1) を取り違えると A・B、C・D の割り当てが逆になります。
• Karatsuba 法の子ノード①②③の順序（A×C、B×D、(A＋B)×(C＋D)）を覚え違えると、図の空欄に別の式を書いてしまいます。

FAQ

解答の論理構成

1. カラツバ法の子ノード作成
   【問題文】には
   「乗算記号の左右にある値を、それぞれ M/2 桁ずつに分けて A、B、C、D の四つの多倍長整数を作る」
   とある。
   ノード「46×134」は M＝2（values 配列の要素数が 2）なので M/2＝1。
   • 46（values＝{6,4}）
     • A＝left(46,1)＝4
     • B＝right(46,1)＝6
   • 134（values＝{14,12}）
     • 134 は 56＋78 の“桁ごとの加算”結果であり、繰り上がり未処理なので
       下位桁が 14、上位桁が 12 で 2 桁扱いになる点に注意。
     • C＝left(134,1)＝12
     • D＝right(134,1)＝14
2. 各子ノードの計算
   同一ノード内での子ノードは
   「① A×C、② B×D、③ (A＋B)×(C＋D)」
   と定義されている（【問題文】より）。
   • ① $A\times C＝4\times 12＝48$ …… これが α
   • ② $B\times D＝6\times 14＝84$ …… これが β
   • ③ $(A＋B)\times (C＋D)$
     • $A＋B＝add(4,6)=10$（繰り上がりはまだ行わない）
     • $C＋D＝add(12,14)=26$
     • よって $10\times 26＝260$ …… これが γ
3. ルート式への代入
   ツリー計算では【問題文】の式
   α×10^k ＋ (γ－α－β)×10^{k/2} ＋ β ……(1)
   を各ノードに適用する。
   今回は k＝2（2 桁）なので
   $10^k＝100,10^{k/2}=10$。
   したがって
   $(①)\times 100+((②)-(③)-84)\times 10+(④)$
   に
   α＝48, γ＝260, α＝48, β＝84 を代入すると
   $48\times 100+(260-48-84)\times 10+84$
   となり、設問の空欄は
   ①48, ②260, ③48, ④84 で確定する。

誤りやすいポイント

• 「桁ごとの加算」をした直後の多倍長整数では 要素が 9 を超えてもそのまま にするルールを忘れ、134 を「1・3・4」と思い込んで分割を誤る。
• M/2 桁で分けるときに 配列添字の大きい方が“左” になることを取り違え、A・B と C・D を逆に設定してしまう。
• (γ－α－β) の計算順序を勘違いし、(α＋β－γ) にしてしまう。

FAQ

解答の論理構成

1. 【問題文】の図3では、層ごとの先頭インデックス layer_top[] を決めるために
   layer_top[i + 1] ← layer_top[i] + ウ
   とあります。ルート層の要素数は 1、その次の層は子ノードが 3 個ずつなので 3^1、
   さらにその次は 3^2 … と増えていきます。
   したがって ウ には “現在の層の要素数”＝pow(3, i − 1) が入ります。
2. 子ノード①の格納位置 tidx を求める行は
   tidx ← layer_top[dp + 1] + エ // 子ノード①へのインデックス
   親ノード i が 1 なら子①は次層の先頭、2 ならその 3 つ後ろ… という規則なので
   オフセットは 3*(i − 1) です。ゆえに エ は 3*(i-1) となります。
3. 子ノード生成3行では、親ノード pe の左右半分を渡します。
   elements[tidx ] ← new_elem(cn, left(オ, cn), left(カ, cn)) elements[tidx + 1] ← new_elem(cn, right(オ, cn), right(カ, cn)) elements[tidx + 2] ← new_elem(cn, lradd(オ, cn), lradd(カ, cn))
   val1 と val2 を左右に分割するので オ と カ には
   親ノードが保持する多倍長整数
   pe.val1 pe.val2
   がそのまま入ればよいことが分かります（順序は左辺・右辺で使い分けるため順不同可）。
4. 以上より
   • ウ：pow(3,i-1)
   • エ：3*(i-1)
   • オ：pe.val1
   • カ：pe.val2
     が解答となります。

誤りやすいポイント

• 層の要素数を 3*dp と誤認する
  （実際には累乗：pow(3, dp − 1)）。
• 子ノードの格納位置を i3 で計算し、1 ずれに気付かない
  （インデックスは 1 から始まるので 3(i − 1) が正）。
• オ と カ に left(pe.val1, cn) のような部分結果を直接書いてしまう
  （分割は new_elem 内で行われる）。
• pow() と shift() を混同し、10 の冪乗と 3 の冪乗を取り違える。

FAQ

解答の論理構成

1. 【問題文】の「最下層のノードは、整数の乗算だけで計算できる。」に従い、mul は 1 桁×1 桁の積です。
   1 の位を取り出すには剰余演算が必要で、表 3 の関数
   「mod(m, k) … m を k で割った剰余を整数で返す。」
   が用意されています。したがって
   el.result.values[1] ← mod(mul, 10)
   が [キ] となります。
2. カラツバ法の再帰計算式 (1) で α, β, γ を「子ノード①, ②, ③の乗算の計算結果」と定義しています。
   ・cidx は「子ノード①へのインデックス」を指しているので
   elements[cidx] が α
   elements[cidx + 1] が β
   elements[cidx + 2] が γ です。
3. s1 ← sub( [ク].result, [ケ].result ) は γ−α を作る処理、
   続く s2 ← sub(s1, elements[cidx + 1].result) で −β を加えて
   γ−α−β が完成します。よって
   ・[ク] には γ を表す elements[cidx + 2]
   ・[ケ] には α を表す elements[cidx]
   を当てはめれば所望の差分が得られます。

• キ：mod(mul, 10)
• ク：elements[cidx + 2]
• ケ：elements[cidx]

誤りやすいポイント

• shift と sub の順序を取り違え、α×10^k と (γ−α−β)×10^{k/2} を逆に配置してしまう。
• 表 3 のインデックスは 1 始まり。cidx + 2 を 2 と誤読し 0 起算で実装すると γ と β が入れ替わる。
• mod(mul, 10) を使わず mul − (mul / 10)*10 などと書いてしまい、字句指定に反して減点される。
• sub(p, q) は “桁ごとの減算” を行うだけで繰り下げが未処理。carry() を呼ばないと中間値が負の桁を持つことに気付かずバグを出す。

FAQ

解答の論理構成

1. 【問題文】では「多倍長整数の演算では、整数の桁ごとの値を、1の位から順に1次元配列に格納して管理する」とあります。
   ➜ 1つの桁につき values 配列に1要素を割り当てる設計です。
2. N 桁の最大値は $10^N-1$ です。同様にもう一方も $10^N-1$ だとすると、積の最大値は
   $(10^N-1)\times (10^N-1)=10^{2N}-2\times 10^N+1$
   となり、$10^{2N}$ 未満です。
3. $10^{2N}-1$ は ちょうど 2N 桁まで しか取りません。したがって、N 桁同士を掛けた結果が 2N+1 桁へ繰り上がることはありません。
4. values 配列には結果の全桁を格納できる必要があるので、最大要素数は
   $2\times N$

誤りやすいポイント

• 繰り上がりを 1 桁余分に見積もって「2N+1」と考えてしまう。
  しかし $9\dots 9\times 9\dots 9$ でも $10^{2N}$ を超えないので誤りです。
• 基数 10 の話を見落とし、ビット数換算で要素数を計算してしまう。
• 「ツリー構造の途中で一時的に桁が増えるのでは？」と心配するケース。
  子計算の結果も最大 2N 桁以内に収まるため追加要素は不要です。

FAQ