基本情報技術者試験の最大の難関はアルゴリズム問題です。
アルゴリズムの解説や勉強法、コツを検索すると「トレースしましょう」と言われます。
たしかに、問題文の意味を理解し、プログラムの動き通りに考え、丁寧にトレースすれば全問正解も容易でしょう。
しかし、問題文の解釈が難しい！プログラムの動きが分からない！穴埋めが分からない！丁寧にトレースする時間がない！と多くの人がなるはずです。
私もそうでした。解説を読めば何となく分かるけど解き方が分からない！という状態で、どうやって読めば本番で合格できるのだろう..と悩んでいました。
そこで、基本情報技術者試験の一合格者として、実際に解く際に「どこに着目して、どういうメモを取って、どういう風にトレースしているのか」を解説してみようと思いました。
本記事では令和元年秋期の過去問を使います。
参考書や各種サイトの丁寧で完璧な解説ではなく、合格者のノートや手元を覗き見る気持ちで読んでください。
導入部分を読む
はじめに「どんなことをするプログラムなのかな？」を確認してみましょう。
ここで分かるのは下記の3点です。
- BitapMatchという関数が出てくるみたい。（Bitap法？知らないな～でOK）
- 「対象文字列」と「検索文字列」の2種類も文字列があって、照合をしていくみたい。
- 0を省略する表現を使うみたい。
このうち特に着目するのは文字列が2種類という点です。
アルゴリズム問題は配列を使った問題が出るのですが、この時点で配列は最低2つ登場しそうですね。
まだメモは不要です。なるべく漢字は書きたくないので配列名が出てくるまで我慢です。
具体例を探す
何となくやりたいことは分かったので、問題文と設問を全体的にざっと見て具体例を探しましょう。
今回は導入部分の直後にあったこの部分が使えそうですね。
はい！ここはメモの出番です。配列名も一緒に出てきてくれてありがたいですね。
配列をメモするときは左右に並べましょう。理由はそれぞれの配列に対して何かしらの処理をする場合の、下方向にメモをしていきたいからです。
このままどうやって照合させていくのか問題文を読み進めてみましょう。
まずは日本語で理解します。
- アルファベットの文字ごとに「ビットマスク」というものを生成するんだな。
- Mask[]という第三の配列が登場するんだな。
- 後半部分のMaskの説明は..ちょっと難しいな。
ちょっと難しいなレベルでも問題ないです。立ち止まらずに読み進めてみましょう。
読み進めるとMask[]に対する具体的な説明が出てきます。
「ちょっと難しいな」と感じる内容には出題者がヒントを出してくれるのでそれにあやかりましょう。
ここで穴抜き問題（空欄「a」）が出てきたので、しっかり理解しながら解いていきます。
空欄「a」を読み進めながら解く
最初の問題は易しい傾向にあるので、問題文の(2)で理解できた人は穴埋めを解いてすぐに次に行ってOKです。
ピンとこなかった人は一緒に考えてみましょう。はじめは時間がかかっても大丈夫です。
今回の具体例のPat[]ではD～Zは登場しないので初期化された「”0”B」のままです。
ビットマスクの作り方は「下位から数えてi番目のビットを1にする」ですね。
※「i」は変数で要素番号や繰り返しの回数を表現するのによく使われます。
他にはkとかjとか。未経験者にとっては馴染みがないと思いますが、資格勉強としてここは深く考えず「そういうもんだ」でOKです。
「i」は変数で、その都度値が変わっていきます。
Pat[]のi=1番目はA、i=2番目はC、、、のように読み解いていきます。
つまりAに着目するとi=1、3、5番にあるので、下位から数えて1、3、5番目のビットを1にすると読解できます。
図2を見てみると「”10101”B」ですね。
もし「下位」が分からなくても具体例を見れば「右側が下位なんだな～」とわかります。
法則が理解できたので穴埋めのBに着目しましょう。
Pat[]の4番目と6番目がBなので「”101000”B」になるので答えは「イ」です。
プログラム1の穴埋めを日本語から解く
読み進めましょう。
プログラミングっぽくなってきましたが、今までで「日本語での処理の理解」はできているので身構えなくて大丈夫です。
入出力から読み取れる新しいキーワードは「文字数」です。
入出力とプログラムはセットで確認していきます。
短めのプログラムに、空欄が2か所で、2つのループがあります。
どんな登場人物（変数や配列）がいるのかとその役割、各ループの処理内容を把握していきます。
登場人物はPat[]、Mask[]、i、PatLenですね。
配列名にLenが付いている変数はその配列の長さ（文字数）を表現していると考えてOKです。LengthのLenです。
今回は値は変化しませんが、プログラムの処理によっては値がどんどん変化するときもあります。
プログラムを見てみるとループが2つあるので一つずつ見ていきます。
一つ目はコメントによると初期化をしているみたいですね。
(2)の説明で「すべての要素を0」で初期化とあるので「ア」が答えです。
初期化が穴埋めになっている場合はラッキー問題です。日本語の説明ベースで解けます。
二つ目のループはちょっと考えてみましょう。
まず変数iの範囲を確認します。今回は1～6(PatLen)です。
i=1の時の動きをトレース
Mask[Index(Pat[i])]はAのビットマスクと日本語訳します。
この時点では初期値のままなのですべて0です。
空欄「c」との論理和の結果、i=1番目、つまり下位から1番目のビットを1に変更しています。
よってこの場合に空欄「c」に入るのは「”1”B」です。
しかし、常に”1”Bにするとi=2の二週目のループも同じ結果になってしまいます。答えにはなりません。
i=2の時の動きをトレース
つぎはCですね。この時点ではCのビットマスクは初期値なのですべて0です。
これを図2の「”10”B」にするためには「”10”B」との論理和とすればよさそうです。
選択肢の「PatLen」はプログラム1では値が変わらないので「6」を代入して、i＝2の場合を考えてみます。答えは「ア」になります。
- ア：”1”Bを1ビット論理左シフト→〇
- イ：”1”Bを2ビット論理左シフト→×
- ウ：”1”Bを5ビット論理左シフト→×
- エ：”1”Bを6ビット論理左シフト→×
- オ：”1”B→×
テクニック的な話だとループ内の空欄には変数が入ることが多いので、アかイと狙いを定めることもできます。
ビット演算の暗算は間違えやすいのでメモ用紙を使ってOKです。桁のズレに注意してください。
次のプログラムを読む
読み進めるとまた別の関数の説明が始まります。
今回はプログラム中の穴埋めはなさそうですが、αやβといかにも問題になっていそうなマークがあります。
やることは同じです。まずは日本語で理解、そして登場人物を確認しましょう。
登場人物は、Text[]、Pat[]、Mask[]、Goal、Status、i、TextLen、PatLenです。
このうち値が変化するのはiとStatusになるので、トレースする際はこの2つに注目していきます。
参考までにこの時点でのメモはこんな感じで取ったりしています。
このくらい整理・把握できたら先に設問を見てみましょう。
「このくらい」を具体的に示すと下記の通りです。
- 日本語ベースで大まかな動き。今回の場合はどの順番に何と何を比べるのか。
- トレースで着目する部分。今回はi回のループと、着目すべきStatusという変数の把握。
- 戻り値。最終的にこの関数はどんな情報を出すのか。
設問2を解く
設問の中にどうやってトレースすればいいかの手順まで書いてあるので参考にします。
どうやらループ2回目と9回目のStatusと、9回目のビットマスクが空欄みたいです。
このうち空欄「e」はこの時点で解けます。
ビットマスクは変化がないので、Text[]の9番目であるAのビットマスクを答えればOKです。
選択肢は省略表現を使っているので、空欄「e」の答えは「キ」になります。
さて、空欄「d」と「f」はトレースする必要がありますが、「f」はちょっと難関ですね。
丁寧にループ9回分トレースすると少し時間がかかってしまう可能性があります。
ここで戦略は3つあります。
- 「f」は一旦置いておいて時間が余ったら戻って解く
- 「d」を解く過程でプログラムを理解してトレースなしで「f」を解く
- がんばってトレースしてみる
おすすめの順番は2→1→3です。
まず、「d」はトレース2回で解けるのでしっかり丁寧に理解しながら進めます。
その過程で理解でき、時間を掛けずに「f」も解けるなら解きます。
解け無さそうなら一旦置いて設問3、または解いていない大問があればそちらを優先します。
時間をかけて1問正解するよりも、他で得点UPを目指す作戦です。
最後に、試験時間が余っていたら頑張ってトレースしてみましょう。
i=1、2の時の動きをトレース
文中の下記を参考にメモを取りつつトレースしていきます。
Statusという変数は1つですが、αの箇所とβの箇所で2回値が変化する点に着目し、i＝1メモは下記のようにとります。
このままi＝2のトレースをしていきます。空欄「d」はメモ中の「Status β」にあたります。
αを実行した直後のStatusの値は設問中にあったのでそのまま記載し、ビットマスクとの論理積を取ったところ「”1”B」となったので答えは「イ」です。
i=9の時の動きをトレース
さて、今回のトレースですがi番目のトレースの際に必要な情報はi-1番目のStatusの値（とビットマスク）でした。
空欄「f」を解くためには8回目のループの際のStatus情報が必要ですが、設問の表に記載してくれています。
丁寧に９回ループを繰り返さなくてもよさそうです。
8回目完了時のStatusは表より「”10”B」ですね。
これを1ビット左に論理シフトすると「”100”B」になります。これと「”1”B」との論理和なのでα完了時のStatusは「”101”B」になります。
βの処理では「”101”B」とビットマスクである「”10101”B」の論理積を求めるので「f」の答えは「”101”B」である「カ」になります。
設問3を解く
設問3は今までと内容が変わってしまいました。
本番では、ざっと見て時間内に解け無さそうだったら他の問題で点数を稼ぐのもありです。
今期の問題数的に設問3を丸々落としても66%なので、ぎりぎり足は引っ張りません。
今回は練習なのでしっかり解いていきます。
どうやら設問2の文字検索ではなく、その前段階（設問１）のビットマスクの生成の仕組みを拡張しようというもののようです。
では、今まで通りまずは日本語での理解と登場人物を確認していきましょう。
プログラム中の穴埋めはない（「ｂ」はすでに回答済み）です。
一つ目のループは初期化で拡張前と変化なしなのでスルーしてOKそうです。
全体を見ると登場人物と役割が変わっていそうです。
新顔のOrifinalPatLenはPat[]の文字数ですね。ここの文字数には [ と ] も含みます。この数だけiを繰り返していて、数字自体の変化はなさそうです。
PatLenの初期値は0です。その後の処理を見ると分岐条件によっては+1していくようです。今までと役割が変わっています。
Modeという変数もあります。詳しい説明はないですが、後続の処理をみると取りうる値は0か1のようです。
今回は分岐が多いのでフローチャートを書くと良いですが、書く前に設問の日本語から処理をつかみましょう。
設問3はプログラムの説明文中に空欄があるタイプです。
早速具体例がありますね。トレースにはこれ（AC[BA]A[ABC]A）を使います。
最初の空欄「g」は文字Aに対するビットマスクです。正規表現をどう表すかはプログラムを見る必要がありそうです。
次の空欄「h」は返却値です。プログラムによるとPatLenになります。今までの設問ではPatLenは一定の値でしたが、今回は値が変わることに注意です。
最後の空欄はPatの中身が変わるのでトレースのし直しになりそうです。
フローチャートを書く
今回は分岐が多いのでフローチャートを書いてみます。
馴染みのない人は身構えてしまうかもしれませんが、「条件に対するyes/noで先が分かれる図」です。性格診断とかでもありそうな感じです。
例えばこんな感じです。最低限自分が分かればよいメモなので、書き方は気にしなくてOKです。
分岐条件を♢ダイヤの形で書いてます。
プログラムを見るとModeは正規表現の中か否かを表しているようです。
そしてPatLenは正規表現の外（Mode0）では常に+1ずつされ、正規表現中では正規表現が始まる「[」で+1されるようです。
日本語での理解ができました。
実はこの時点でこの関数の返却値である空欄「h」は解くことができます。
「AC[BA]A[ABC]A」のうち正規表現外の文字は4つ。そして正規表現は2つなので合計値の6が返却されます。
空欄「h」の答えは「イ」になります。
次に表を書きます。これは変数の値を更新していくためのものです。
必要なのはi、Mode、PatLenで、あとはビットマスク用の演算のためのメモ領域も空けておきましょう。
i=1の時の動きをトレース
一文字目（i=1周目）は「A」なのでModeは0のまま、PatLenは+1されて1になります。
よってAのビットマスクは”1”Bを0ビット左に論理シフトした値との論理和になります。
i=2の時の動きをトレース
二文字目（i=2周目）は「B」なのでModeは0のまま、PatLenは+1されて2になります。
着目している（空欄問題になっている）のは「A」のみなのでビットマスクの演算はスキップしてOKです。
i=3の時の動きをトレース
三文字目（I=3周目）は「[」なのでModeは1になり、PatLenは+1されて3になります。
ビットマスクは2文字目同様にスキップです。
i=4の時の動きをトレース
四文字目は「B」なので、Modeが1なので処理は行わずビット演算です。
ビット演算はスキップします。
i=5の時の動きをトレース
五文字目でようやく「A」が出てきました。Modeは1のまま、現在のPatLenの値は3なので、”1B”をPatLen-1、つまり2左に論理シフトして論理和を求めます。
この時点での「A」のビットマスクは”101”Bです。
[]の中ではPatLenの値が一定なので、今回の例だと「A」のビットマスクも「B」のビットマスクも下位から3番目は1になります。
このようにPatLenの値を追っていくとビットマスクが完成できそうです。
i=6以降の時の動きをトレース
この時点で空欄「g」の選択肢は「ア」と「カ」に絞れました。
このまま表を埋めていき、「A」に関するビットマスクを検討します。
i＝7の時点で選択肢が「カ」に絞れるので次の問題に進みます。
設問3の空欄「i」を解く
もう一度設問に関する問題を読みます。
二連続で正規表現開始が来たり、正規表現終了がきたらどうなりますか？ということを聞いています。
一見混乱してしまいそうですが、今までの問題で処理の流れは分かっています。
ポイントは下記のとおりです。
- 正規表現が始まったらModeを1にして、終わったら0にする
- 正規表現始まりの記号で+1し、Mode1中は一定
この日本語を基に表のメモだけで選択肢を絞っていきます。
i＝6の時点で選択肢は「ウ」に絞れました。
おわりに
長丁場お疲れさまでした。
最後まで読んでくださりありがとうございます。
問題は解けましたか？
今回紹介した解き方がすべてのアルゴリズム問題に適応できるわけではありませんが、一つ一つ読み解いていけば合格へ近づきます。
少しでもアルゴリズム問題に対する苦手意識が減ってくれると嬉しいです。
最後に公式の講評を貼っておきます。ご自身の正答率と比較してみてください。
コメント