09 過去問演習ー5（全分野 横断・5周目）

正解：エ

8×8のマス目（配列A）の模様を、別の8×8のマス目（配列B）に移しかえる問題です。二重ループで i も j も 0〜7 まで動くので、Aの全64マスを1つずつBのどこかへ配るという処理になります。a に入るのは、その「配り先の住所の決め方」です。

まず、模様がどう変わったかを見る

配列Aの★の並びを言葉にすると、こんな形です。

• いちばん上の行（i=0）に、横向きの棒が1本
• 左から2列目（j=1）に、上から下までの縦の棒が1本
• まん中あたりの行（i=3）に、短い横棒が1本

アルファベットの「F」を思い浮かべてください。実行後の配列Bを見ると、その棒が全部90度たおれています。

• 上から2行目（i=1）に、横いっぱいの棒
• いちばん右の列（j=7）に、縦の棒
• j=4 の列に、短い縦棒

Aの「縦の棒」がBでは「横の棒」に、Aの「横の棒」がBでは「縦の棒」になっています。つまりこれは図形を時計回りに90度回転させた、ということです。

代表の1マスで確かめる（これが一番速い）

全64マス調べる必要はありません。特徴的な1マスを選んで、選択肢に当てはめるだけで答えが出ます。

使いやすいのは、Aの左上の★＝A(0, 1)（i=0、j=1）です。ではこの★はBのどこにあるはずでしょうか。Aの「上の横棒」はBの「右の縦棒」になったので、この★はBの右上のあたり、具体的には B(1, 7) のはずです（実行後の図で、1行目の右端に★がありますね）。

では、i=0、j=1 を各選択肢の式に入れて、B(1, 7) になるものを探します。

エだけが当たりました。念のため、もう2マスで検算しておきましょう。

• 縦の棒：Aの j=1 の列にある★たち A(0,1) … A(7,1) は、エの式で B(1, 7−i) となり、i が 0〜7 と動くと行はずっと1のまま、列が 7,6,5,…,0 と動きます。Bの1行目が左端から右端まで全部★になる、ということ。実行後の図とぴったりです。✔
• 短い横棒：Aの i=3 の行にある★たち A(3,1) … A(3,4) は、B(j, 7−3) ＝ B(j, 4)。j が 1〜4 と動くので、Bの4列目に、1行目から4行目まで縦に★が並びます。これも図のとおり。✔

3か所すべて合ったので、答えは エ で確定です。

ほかの選択肢は「どんな変形」なのか

実は不正解の3つも、それぞれ意味のある変形になっています。中身を知っておくと引っかかりません。

• ア B(7−i, 7−j)：行も列も裏返すので180度回転。Fが上下左右ひっくり返った形になります。
• イ B(7−j, i)：エとよく似ていますが、こちらは反時計回りの90度回転。回転の向きが逆です。エと迷ったら、必ず1マス入れて確かめましょう。
• ウ B(i, 7−j)：行はそのままで列だけ裏返すので、左右の鏡うつし。回転していないので、Aの横棒は横棒のまま。今回のように棒の向きが変わる図には合いません。

速解法

1. 棒の向きが変わっていたら「回転」、変わっていなければ「鏡うつし」と、まず当たりをつける。
2. 回転なら、特徴的な★を1個だけ選んで、移動前 (i, j) と移動後の座標をメモする。
3. 選択肢に i、j の数字を代入して、その座標になるものを選ぶ。ふつう1マスで2〜3個消え、残りは2マス目で決着します。

ちなみに「時計回り90度＝B(j, 7−i)」「反時計回り90度＝B(7−j, i)」「180度＝B(7−i, 7−j)」はよく出る組み合わせです。ただし丸暗記より、その場で1マス代入して確かめるほうが確実で速いですよ。

正解：ア

逆ポーランド表記法（後置記法）は、「計算する数を先に並べて、記号（演算子）を後ろに置く」書き方です。ふだん私たちが書く A+B（中置記法）は、逆ポーランドでは AB+ になります。「AとBを持ってきて、それから足す」という順番です。

ステップ1：式を「かたまり」に分ける

問題の式は「分数」の形をしています。分数は割り算です。つまり全体はこういう形です。

• 分子（上）… (A+B) と (C+D) を掛けたもの
• 分母（下）… A−D
• 全体 … 分子 ÷ 分母

ステップ2：小さいかたまりから逆ポーランドに直す

ステップ3：大きいかたまりを組み立てる

1. 分子は「AB+ の結果」と「CD+ の結果」を掛けるので、2つを並べてから × を置く → AB+CD+×
2. 全体は「分子の結果」と「AD− の結果」を割るので、2つを並べてから ÷ を置く → AB+CD+×AD−÷

これが選択肢アと一致します。

スタックで確かめる（コンピュータのやり方）

逆ポーランドは、左から1つずつ読んで「文字なら積む・記号なら上から2つ取り出して計算し、結果を積む」だけで計算できます。アを実際にたどってみます（スタックは左が下）。

最後に問題の式そのものが残りました。アで正解です。

なぜ他の選択肢は違うのか

• イ：× が後ろのほうに移動していて、記号の並びが + + − × ÷ になっています。この順でスタックをたどると、− の時点で「(C+D) から A を引く」という、問題文にない引き算が起きてしまいます。掛け算の相手を間違えた形です。
• ウ：ABCD++ と最初に文字を4つ並べています。この形だと最初の + は「C+D」、次の + は「B+(C+D)」となり、B+C+D という和ができてしまいます。(A+B) と (C+D) を別々に作れていません。
• エ：ウと同じく文字を4つ並べたうえに、最後が ÷ … × の順です。分数（割り算）が最後にくるはずなのに、掛け算が最後になっているので、式全体の形が「何かの掛け算」になってしまい別物です。

速解法

• いちばん最後の記号＝いちばん最後にする計算。この式は「最後に分子÷分母」なので、答えは必ず ÷ で終わります。これだけでエが消えます。
• 文字の並びを見る。(A+B) と (C+D) を別々に足すなら AB+CD+ と「2文字＋記号」が2組になるはず。ABCD++ のように文字が4つ続く形はカッコの区切りが消えているので×。これでウも消えます。
• 残ったアとイは × の位置だけの違い。分子（掛け算）を先に完成させてから割るので、× は AD− より前にあるアが正解、と判断できます。

正解：イ

スタックは、本を机に積み上げていくイメージのデータ構造です。取り出すときは一番上（＝最後に積んだもの）から取るので、後入れ先出し（LIFO：Last In, First Out）と呼ばれます。この特徴を表す用語はイの LIFO です。

他の選択肢がなぜ違うか。

• ア FIFO（First In, First Out：先入れ先出し）＝先に入れたものから取り出す。これはキューの特徴です。
• ウ LILO（Last In, Last Out：後入れ後出し）＝じつは「先に入れたものが先に出る」FIFO と同じ意味で、キュー側を言い換えた語。スタックの特徴ではありません。
• エ LRU（Least Recently Used）＝「最も長く使われていないもの」を選ぶ、キャッシュの入れ替え方式などで使う考え方で、スタックの特徴とは無関係です。

速解法：「スタック＝LIFO（積み上げ、上から取る）」「キュー＝FIFO（行列、前から取る）」の2語をセットで暗記。LILO・LRU はひっかけなので、スタック＝LIFO と即答できます。

正解：ウ

スタックは「あと入れ先出し（LIFO）」。A,B,C,D が順に到着し、各データは「到着したらすぐ積む(push)か、あとで積む」、そして「積んだ一番上から取り出す(pop)＝それが出力」になります。到着順は必ず A→B→C→D です。各選択肢の出力列が作れるか、push(＋)とpop(−)の手順で試します。

ウ C,B,D,A が作れるか

ぴったり作れました。よってウが正解。

なぜ他が作れない？（どこで詰まるか）

• ア A,D,B,C…A を出したあと D を出すには B,C,D を積んで上の D を取る。その後は上が C なので次に B は取れず、B より先に C しか出せない。B,C の順が作れず不可。
• イ B,D,A,C…B を出す（A,B積んでB取る）→ A が下に残る。次に D を出すには C,D を積んで D を取る。次は A を出したいが上は C。A の上に C がいて取り出せず不可。
• エ D,C,A,B…先に D を出すには A,B,C,D を全部積む。取り出すと上から D,C,B,A の順しか出せない。3番目に A、4番目に B は無理（B が先）。不可。

速解法：スタックで作れない並びには「231型（あとから来た大きい数の前に、それより小さい2つが逆順で出てくる）」が現れます。A→B→C→D を 1→2→3→4 と読み替え、途中に「大・小・中」の逆転がある列（ア=1423, イ=2413, エ=4312）は不可、と当たりを付けられます。

正解：ウ

この関数のルールも2行だけです。

• n が 1 以下なら、無条件で 1 を返して終わる（再帰の終わり）。
• そうでなければ、今の n に f(n−1) の答えを足して返す。

さっきの互除法と違うのは、return n + f(n−1) のように n + がくっついている点です。だから答えは「奥から戻ってくる値に、自分の n を足す」形で積み上がります。

ステップ1：奥へもぐる（呼び出しの連鎖）

• f(5) = 5 + f(4)
• f(4) = 4 + f(3)
• f(3) = 3 + f(2)
• f(2) = 2 + f(1)
• f(1) … n が 1 以下なので 1 を返す（ここで止まる）

ステップ2：手前へ戻る（値の確定）。いちばん奥から順に数字が決まっていきます。

したがって f(5) は 15 です。式をぜんぶ展開すると 5 + 4 + 3 + 2 + 1 = 15 で、要するに1 から n までの足し算をする関数だと分かります。

なぜ他の選択肢が違うか

• ア（6）：f(3) の値。途中の階で数え終わってしまった形です。
• イ（9）：たとえば f(1) が返す 1 を足し忘れて 5+4 だけにする、といった数え落としで出やすい値。n ≦ 1 のとき返すのは 0 ではなく 1 です。
• エ（25）：n × n（5×5）と勘違いした形。この関数は掛け算ではなく足し算です。

速解法：return n + f(n−1) で終わりが 1 なら、それは 1 + 2 + … + n の合計です。公式 n × (n + 1) ÷ 2 を使えば 5 × 6 ÷ 2 = 15 と一発。似た形の return n × f(n−1) なら階乗（5×4×3×2×1 = 120）になるので、「+ なら合計、× なら階乗」とセットで覚えておくと、トレースせずに答えを出せます。トレースする場合も、必ずいちばん奥（終了条件）から手前へ値を確定させるのがミスを防ぐコツです。

正解：エ

こちらは割り算を使わない互除法です。「大きいほうから小さいほうを引く」を、2つの数が等しくなるまで繰り返します。等しくなった値が最大公約数です。

流れ図の動きを言葉にすると、こうなります。

• 最初に L に A（876）、S に B（204）を入れる。
• ひし形で L と S を比べる（＝これが「比較」1回）。
• L > S なら L から S を引いて L を更新し、比較へ戻る。
• L < S なら S から L を引いて S を更新し、比較へ戻る。
• L = S になったら出力して終了。

聞かれているのは「比較が何回で終わるか」なので、ひし形を通った回数を数えます。最後の「等しかった」という比較も、ちゃんと1回に数えるのがポイントです。

よって比較の回数は 11 回です。

検算：876 = 12×73、204 = 12×17 なので最大公約数は 12。表の最後で L も S も 12 になっているので、トレースは正しいと確認できます。

なぜ他の選択肢が違うか

• ア（4）：最初の「876 から 204 を4回引く」ところだけ数えて止めた形。60 になったあとに L と S が入れかわって、今度は S 側を減らす作業が続きます。
• イ（9）：途中の数え落とし。とくに引き算をしない最後の比較や、L と S が入れかわる境目を飛ばすとこうなりがちです。
• ウ（10）：引き算をした回数（10回）を答えてしまった間違い。引き算は10回ですが、比較はそのあとの「等しい」を含めて11回です。ここが最大のひっかけポイント。

速解法：割り算の互除法で「商」を先に出すと、引き算の回数がまとめて分かります。876 ÷ 204 = 商4 余り60、204 ÷ 60 = 商3 余り24、60 ÷ 24 = 商2 余り12、24 ÷ 12 = 商2 余り0。引き算の回数は商の合計ですが、最後の段はちょうど割り切れるので実際には最後の1回を引く手前で等しくなります。4 + 3 + 2 + 2 − 1 = 10回の引き算、それに終了判定の比較1回を足して 11回。表を全部書かなくても検算できます。試験では「比較回数を聞かれたら、引き算回数 ＋ 1」と覚えておくと安全です。

正解：イ

この流れ図は、割り算の筆算をコンピュータにやらせるとどうなるか、を表しています。やっていることはとてもシンプルで、「x から y を引けなくなるまで引き続け、何回引けたかを数える」だけです。

ステップ1：変数の役割をつかむ

• q ← 0 … q は最初 0。これは引いた回数を数えるカウンターです。
• r ← x … r に x を入れる。これは今の残りです。

ステップ2：ループの動きを読む

1. 判断 r < y：「残りが y より小さい？」
2. Yes（小さい）なら終了。もう y を引けないので、そこで止まる。
3. No（まだ y 以上）なら、r ← r − y（残りから y を引く）と q ← q + 1（引いた回数を1増やす）をして、判断に戻る。

つまり「引けるうちは引いて、回数を数える」。これは小学校で習う割り算そのものです。「17 の中に 5 はいくつある？」を、17−5−5−5＝2 と引いて確かめるのと同じことをしています。

ステップ3：実際に数字でトレースする

x=17, y=5 でやってみます。

終わったとき q = 3、r = 2。一方 17 ÷ 5 = 商 3 余り 2 です。ぴったり一致します。

したがって q は x ÷ y の商、r は x ÷ y の余り。これはイです。

なぜ他の選択肢は違うのか

• ア：q と r の中身が逆です。q は「引いた回数」を数えているのだから商であって、余りにはなりません。上のトレースでも q=3（商）、r=2（余り）でした。商と余りを取り違えた引っかけで、いちばん多い間違いです。
• ウ・エ：どちらも「y ÷ x」になっています。しかし流れ図では r ← x と割られる数の側に x が入り、r − y と引く数が y です。引かれる側が x なので、計算しているのは x ÷ y であって y ÷ x ではありません。

速解法

• x=17, y=5 のような小さい数を自分で入れて2〜3周まわすのが最速で確実です。流れ図の問題は「眺めて考える」より「手で動かす」ほうが速く、間違えません。
• それも面倒なら役割で判断します。+1 されている変数は回数＝商、引き算されて減っていく変数は残り＝余り。この対応を覚えておくと一瞬で q＝商・r＝余りと分かります。
• どちらが「割られる数」かは r ← x（最初に r に入るほう）を見ればすぐ分かります。ここに x が入っているので x ÷ y です。

正解：イ

2分探索は、並んでいるデータのまん中を見て、探す値がその前half・後half どちらにあるかを判断し、範囲を半分に捨てていく探し方です。「1回調べるごとに、候補が半分になる」——ここがすべての出発点です。

ステップ1：最大何回で見つかるかを考える

データが n 個あるとき、調べるたびに候補が半分になるので、残りの候補は次のように減ります。

候補が1個になったら終わりなので、「n を何回半分にすれば1になるか」が最大の回数です。これは log2 n（2を何回掛けたら n になるか、の逆）で表せます。細かく言えば最大探索回数はおよそ log2 n + 1 ですが、この問題では「+1」の部分は後で消えるので気にしなくて大丈夫です。

ステップ2：データが4倍になったら？

データが n から 4n に増えたときの回数の差を見ます。

• 増える前：約 log2 n 回
• 増えた後：約 log2 (4n) 回

ここで「4n を1になるまで半分にする」のは、「まず4nを半分にして2n、もう一度半分にして n、そこから先は元と同じ」という手順です。つまり最初に2回だけ余分に半分にすれば、あとは元の n の場合とまったく同じ。よって増えるのは 2回だけです。

式で書くと log2(4n) = log2 4 + log2 n = 2 + log2 n となり、やはり差はちょうど2回。答えはイです。

ステップ3：具体的な数で確かめる

データが1,000個でも100万個でも、4倍にしたときに増えるのはいつも2回。データ量に関係なく一定なのが2分探索の強みです。

なぜ他の選択肢は違うのか

• ア（1回増える）：これはデータが2倍になったときの答えです。2倍＝半分にする回数が1回増える、4倍＝2回増える。「4倍」を「2倍」と読み違えると、この選択肢を選んでしまいます。
• ウ（約2倍になる）：回数そのものが2倍になる、という意味です。上の表で見たとおり、1,024個で10回→4,096個で12回であって、20回にはなりません。「データが増えた倍率」と「回数が増える倍率」を混同した選択肢です。
• エ（約4倍になる）：「データが4倍だから回数も4倍」という、いちばん素直だけれど間違った考え方です。これが成り立つのは線形探索（先頭から1個ずつ調べる方法）のほう。線形探索なら最大 n 回なので、データ4倍＝回数も約4倍になります。2分探索と線形探索の性質の違いを問う引っかけです。

速解法

• 「2倍で+1回」だけ覚える。4倍＝2倍の2回分なので +2回、8倍＝2倍の3回分なので +3回。これで一瞬で解けます。
• 迷ったら 1,024個 → 10回 という数字を1つ暗記しておき、その場で表を作って確かめると確実です（1024は2を10回掛けた数）。
• 2分探索の回数は「掛け算ではなく足し算で増える」と覚えておくと、ウ・エのような「◯倍になる」系の選択肢は読んだ瞬間に消せます。データが増えても回数がほとんど増えないことこそ、2分探索が使われる理由だからです。

正解：ウ

この問題は「ハッシュ表にデータを順番に入れていったとき、どのデータで最初に場所の取り合い（衝突）が起きるか」を聞いています。ハッシュ表とは「データから計算した番号の場所にしまう入れ物」のことで、ここではしまう場所の番号を「データを 8 で割った余り」で決めます。

ステップ1：16進数を8で割った余りの求め方

データは 16 進数（0〜9 のあとに A=10, B=11, C=12, D=13, E=14, F=15 と続く数え方）で書かれています。まともに 10 進数へ直してもよいのですが、実は下 1 桁だけ見れば十分です。理由は、16 進数の上の桁は必ず 16 の倍数（16、256、…）を表し、16 も 256 も 8 で割り切れるからです。つまり上の桁は余りに影響しません。

• 例：1A は 10 進で 1×16 + 10 = 26。26 ÷ 8 = 3 余り 2。
• 下 1 桁の A（=10）だけで計算しても 10 ÷ 8 = 1 余り 2。同じ答えになる。

なので「下 1 桁を 8 で割った余り」を見るだけで解けます。

ステップ2：順番に表へ入れていくトレース表

8 番目の B2 で、1 番目に入れた 1A と同じ場所 2 に入ろうとします。ここが最初の衝突です。よって答えは ウ。

なぜ他の選択肢が違うのか

• ア（54）…余りは 4。それまでに場所 4 を使ったデータはなく、すんなり入ります。
• イ（A1）…余りは 1。場所 1 も空いたままなので衝突しません。
• エ（B3）…余りは 3 で、確かに 3 番目の 3B とぶつかります。しかし順番は 9 番目で、8 番目の B2 より後。問題は「最初に衝突するもの」なので不正解です。ここが一番ひっかかりやすい罠で、「衝突するデータ」をすべて探して満足すると エ を選んでしまいます。

速解法

1. 「8 で割った余り」＝ 16 進数の下 1 桁だけ見る（上の桁は 8 で割り切れるので無視）。
2. 下 1 桁が 0〜7 ならそのまま、8〜F なら 8 を引く。A→2、B→3、E→6、F→7。
3. 余りを左から順に書き出す：2, 5, 3, 4, 6, 1, 7, 2, 3。
4. 左から読んで最初に同じ数字が 2 回目に出てきた所を指す。2 が二度目に出るのは 8 番目 → B2。

余りの列を書き出してしまえば、あとは「同じ数字の 2 回目探し」だけなので 30 秒で解けます。