応用情報技術者 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. ウ：pow(3,i-1) の理由

• 各層のノード数はルート層が1個で、1つ上の層の各ノードが3個の子ノードを持つため、層番号を $m$ とすればその層の要素数は $3^{m-1}$ です。
• layer_top[i+1] に入れる値は「次の層の左端の添字」なので、現在の層の要素数を足す必要があります。ループ変数がiのとき、現在の層の要素数は $3^{i-1}$ です。
• pow(m,k) が整数のべき乗を返す関数であることから、コード表記ではpow(3,i-1) が適切です。
• 検算：図2の例ではlayer_topが {1,2,5} になるので、1 + pow(3,0) = 2、2 + pow(3,1) = 5と一致します。

1. エ：3*(i-1) の理由

• 図3内の内側ループは親ノードごとに処理を行い、各親から3個の子ノードを生成します。elements[] は層ごとに左から順に格納するため、次の層でのi番目の親の子ノードは「次の層の左端」から過去の親が作った子ノード分だけ離れた位置に置かれます。
• 1番目の親（i=1）の子ノードはオフセット0から始まる必要があるので、i番目の親の子ノード開始オフセットは3*(i-1) です。したがってtidx = layer_top[dp+1] + 3*(i-1) が正しい位置を指します。
• 検算：図2でdp=1, i=1のときtidx = layer_top[2] + 0 = 2となり、elements配列上で12×56, 34×78, 46×134が続いて格納される配置に一致します。

1. オ／カ：pe.val1, pe.val2の理由（順不同）

• 図3の直前で pe ← elements[layer_top[dp] + (i − 1)] として親ノードを取得しており、親ノード構造体の乗算対象は pe.val1 と pe.val2 に格納されています。さらに cn ← pe.N / 2 により分割幅が求まっています。
• left(p, k), right(p, k), lradd(p, k) の説明は「pについて、valuesの添字が大きい方のk個／小さい方のk個を返す」や「add(left(p,k), right(p,k)) の結果を返す」とあります。これらは親ノードのval1/val2に対して呼ばれており、分割（left/right/lradd）は呼び出し側で行われています。つまりnew_elemの引数は既にleft(...,cn) / right(...,cn) / lradd(...,cn) によって得られた部分値であって、new_elemの内部で分割されるわけではありません。
• したがってleft(...,cn) やright(...,cn) の第1引数として渡すのはpe.val1およびpe.val2である必要があり、オ／カにはpe.val1, pe.val2の二つが入ります（順不同）。

• ウ：pow(3,i-1) は各層の要素数 $3^{i-1}$ に対応する。図2で {1,2,5} が得られる。
• エ：3*(i-1) はi番目の親の子ノードが次層で先頭から3*(i-1) 個分離れていることを表す。
• オ：pe.val1、カ：pe.val2（left/right呼び出しはnew_elemの外側で行われるため、引数は親ノードのval1/val2である）。

誤りやすいポイント

• powの指数を一つずらしてpow(3,i) やpow(3,dp) としてしまう（ルート層が1個であることを見落とす）。
• 子ノード開始オフセットを3*iとしてしまい、i=1のときオフセットが3になってしまう（オフセットは0始まり）。
• 分割処理をnew_elemの内部で行うと誤解し、new_elemに親ノード全体peを渡すように書く。実際はleft()/right()/lradd() が呼び出し側で適用される。
• left/rightの意味（leftは添字が大きい方＝上位桁、rightは添字が小さい方＝下位桁）を逆に解釈する。
• 配列・添字が1から始まる仕様を忘れて0ベースで考えてしまう（図中の添字計算でオフバイワンを起こす）。

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