こうすりゃ解ける! 2019年度秋期 (令和元年度) 基本情報技術者試験の午後問題を徹底解説


2020-03-16 更新

2019 年 10 月 20 日(日)に実施された 令和元年度 秋期 基本情報技術者試験 の 午後問題 の中から、必須問題である問 8「データ構造及びアルゴリズム」の解き方を解説します。

テーマは「 Bitap 法による文字列検索」です。

ありきたりの解説には、飽き飽きしているでしょうから、「こうすりゃ解ける!」という解法のテクニックと心構えを伝授させていただきます。

error 本記事ではわかりやすいよう、問題に背景色や下線などを入れています

一見して超難しそうな問題の対処方法を伝授します

今回の試験を受験された方は、この問題を見て「何これ! Bitap 法なんて知らない! 超難しそう!」と思われたでしょう。

基本情報技術者試験のアルゴリズムの問題には、時々こういう超難しそうな問題が出ることがあります。これまでにも「ガウスの消去法」「ニュートン法」「ダイクストラ法」など、超難しそうな問題が出たことがあります。

 

でも、ご安心ください。一見して超難しそうな問題ほど、設問の内容は簡単なのです。

なぜなら、アルゴリズムの問題は、受験者全員が解く必須問題だからです。

もしも、設問も超難しかったら、合格率が極端に下がってしまいます。試験を運営する側としては、そんなことはできないはずです。

 

それでは、この手の問題は、どうやって解いたらよいのでしょうか?

この記事では、その秘訣を伝授させていただきます。

それでは、設問 1 から解いて行きましょう。問題、設問、解答群を以下に示します。

問 8 次のプログラムの説明及びプログラムを読んで,設問 1 ~ 3 に答えよ。

〔プログラムの説明〕

 関数 BitapMatch は,Bitap 法を使って文字列検索を行うプログラムである。
 Bitap 法は,検索対象の文字列(以下,対象文字列という)と検索文字列の照合に,個別の文字ごとに定義されるビット列を用いるという特徴をもつ。

 なお,本問では,例えば 2 進数の 16 ビット論理型の定数 0000000000010101 は,上位の 0 を省略して “10101”B と表記する。

(1)
 関数 BitapMatch は,対象文字列を Text[] に,検索文字列を Pat[] に格納して呼び出す。配列の要素番号は 1 から始まり, Text[] の i 番目の文字は Text[i] と表記する。Pat[] についても同様に i 番目の文字は Pat[i] と表記する。対象文字列と検索文字列は,英大文字で構成され,いずれも最長 16 文字とする。
 対象文字列 Text[] が “AACBBAACABABAB”,検索文字列 Pat[] が “ACABAB” の場合の格納例を,図 1 に示す。
図 1 対象文字列と検索文字列の格納例
(2)
 関数 BitapMatch は,関数 GenerateBitMask を呼び出す。
 関数 GenerateBitMask は,文字 “A” ~ “Z” の文字ごとに,検索文字列に応じた ビット列(以下,ビットマスクという)を生成し,要素数 26 の 16 ビット論理型配列 Mask[] に格納する。Mask[1] には文字 “A” に対するビットマスクを, Mask[2] には文字 “B” に対するビットマスクを格納する。このように Mask[1] ~ Mask[26] に文字 “A” ~ “Z” に対応するビットマスクを格納する。

 関数 GenerateBitMask は, Mask[] の全ての要素を “0”B に初期化した後,1 以上で Pat[] の文字数以下の全ての i に対して,Pat[i] の文字に対応する Mask[] の要素である Mask[Index(Pat[i])] に格納されている値の,下位から数えて i 番目のビットの値を 1 にする。

 関数 Index は,引数にアルファベット順で n 番目の英大文字を設定して呼び出すと,整数 n (1 ≦ n ≦ 26 ) を返す。

(3)
 図 1 で示した, Pat[] が “ACABAB” の例の場合,関数 GenerateBitMask を実行すると, Mask[] は図 2 のとおりになる。
図 2 図 1 で示した Pat[] に対する Mask[] の値
(4)
 関数 GenerateBitMask の引数と返却値の仕様は,表 1 のとおりである。
表 1 関数 GenerateBitMask の引数と返却値の仕様
引数/
返却値
データ型 入力/
出力
説明
Pat[] 文字型 入力 検索文字列が格納されている 1 次元配列 16 ビット
Mask[] 16 ビット
論理型
出力 文字 “A” ~ “Z” に対応するビットマスクが格納される 1 次元配列
返却値 整数型 出力 検索文字列の文字数

  〔プログラム 1 〕
  ○整数型関数 : GenerateBitMask(文字型: Pat[], 16 ビット論理型: Mask[])
  ○整数型 : i, PatLen

  ・ PatLen [] ← Pat[] の文字数
  ■ i: 1, i ≦ 26, 1
  | ・Mask[i] ←   b    /* 初期化 */
  ■
  ■ i: 1, i ≦ PatLen, 1
  | ・Mask[Index(Pat[i])] ←   c   と
  |                   Mask[Index(Pat[i])] とのビットごとの論理和
  ■
  · return (PatLen)

設問 1 プログラムの説明及びプログラム 1 中の      に入れる正しい答えを,解答群の中から選べ。

a に関する解答群
ア 0000000000000101  
イ 0000000000101000
ウ 0001010000000000  
エ 1010000000000000

b に関する解答群

ア  "0"B
イ  "1"B
ウ  "1"B を Pathen ビットだけ論理左シフトした値
エ  "1"B を (Pathen - 1) ビットだけ論理左シフトした値
オ  "1111111111111111"B

c に関する解答群

ア  "1"B を (i - 1) ビットだけ論理左シフトした値
イ  "1"B を i ビットだけ論理左シフトした値
ウ  "1"B を (Pathen - 1) ビットだけ論理左シフトした値
エ  "1"B を PatLen ビットだけ論理左シフトした値
オ  "1"B

秘訣 1:
説明文とプログラムを対応付ける

プログラム全体の仕組みがわからなくても、プログラムの説明文とプログラムを対応付けると、空欄に何を入れればよいかがわかる場合があります。

この問題では、空欄 b が正にそれです。

プログラムの説明に「 Mask[] のすべての要素を “0”B に初期化」とあり、それがプログラムの空欄 b に該当します。

〔プログラムの説明〕

 関数 GenerateBitMask は, Mask[] の全ての要素を “0”B に初期化した後,1 以上で Pat[] の文字数以下の全ての i に対して,(中略)

ご丁寧に、というか大ヒントとして、「/* 初期化 */」というコメントまで付けられています。


  〔プログラム 1 〕
  ■ i: 1, i ≦ 26, 1
  | ・Mask[i] ←   b    /* 初期化 */

空欄 b の正解は、選択肢アです。

秘訣 2:
問題に示された具体例をヒントにして考える

今度は、プログラムの空欄 c に何が入るかを、説明文と対応付けて考えてみましょう。

〔プログラムの説明〕

 関数 GenerateBitMask は, Mask[] の全ての要素を “0”B に初期化した後,1 以上で Pat[] の文字数以下の全ての i に対して,Pat[i] の文字に対応する Mask[] の要素である Mask[Index(Pat[i])] に格納されている値の,下位から数えて i 番目のビットの値を 1 にする。

この説明文を見る限り、空欄 c に入るのは「下位から数えて i 番目のビット を 1 にした値」であり、

i が 1 なら 0000000000000001
i が 2 なら 0000000000000010
i が 3 なら 0000000000000100

のはずです。0000000000000001 を i – 1 だけ左論理シフトすればよいでしょう。

ところが、プログラムを見ると「空欄 c と Mask[Index(Pat[i])] とのビットごとの論理和」になっています。なぜでしょう?


  〔プログラム 1 〕

  ■ i: 1, i ≦ PatLen, 1
  | ・Mask[Index(Pat[i])] ←   c   と
  |                   Mask[Index(Pat[i])] とのビットごとの論理和
  ■

こういうときに頼りになるのが、問題に示された具体例です。

具体例を見ると「そういうことか!」とわかる場合があります。コメントも大ヒントですが、具体例も大ヒントなのです。

以下の具体例を見ると、”ACABAB” の先頭(先ほどのプログラムで i = 1 )の “A” に対応するビットマスクが、
0000000000000001 ではなく、
0000000000010101 になっています。

〔問題に示された具体例〕

(3)
 図 1 で示した, Pat[] が “ACABAB” の例の場合,関数 GenerateBitMask を実行すると, Mask[] は図 2 のとおりになる。
図 2 図 1 で示した Pat[] に対する Mask[] の値

「 えっ、何これ?」
「 1 が 1 個でなくて 3 個ある...」
「 ...あっ、そういうことか!」
「 “ACABAB” の中に “A” が 3 個あるから、それを論理和で重ね合わせているんだ!」

とわかるでしょう。

つまり空欄 c は、0000000000000001 を i – 1 だけ論理左シフトするだけでなく、それまでに得られているビットマスクと論理和で重ね合わせるのです。

したがって、正解は選択肢アです。

PR

秘訣 3:
すぐに解けない設問は後回しにする

空欄 a を飛ばして、空欄 b と空欄 c を先に解きました。これは、空欄 a の穴埋めは、先に空欄 b と空欄 c を解かないとできないからです。

このように、もしも順番通りに解いてできない設問があった場合は後回しにして、先の設問を解いてみましょう。それによって、後回しにした設問が解ける場合があるからです。

 

空欄 b と空欄 c を解いたことで、ビットマスクを作る方法がわかりました。

空欄 a には、 “B” に対応するビットマスクが入ります。

問題に示された “ACABAB” では、先頭から 4 番目と 6 番目に “B” が登場します。したがって、

0000000000001000 と
0000000000100000 を論理和で重ね合わせた
0000000000101000 が “B” に対応するビットマスクです。

正解は、選択肢イです。

マスク

秘訣 4:
具体例をコツコツとトレースすればできる

それでは、設問 2 に進みましょう。問題、設問、解答群を以下に示します。

〔関数 BitapMatch の説明〕

(1)
 Text[] と Pat[] を受け取り, Text[] の要素番号の小さい方から Pat[] と一致する文字列を検索し,見つかった場合は,一致した文字列の先頭の文字に対応する Text[] の要素の要素番号を返し,見つからなかった場合は,-1 を返す。
(2)
 図 1 の例では, Text[7] ~ Text[12] の文字列が Pat[] と一致するので,7 を返す。
(3)
 関数 BitapMatch の引数と返却値の仕様は,表 2 のとおりである。
表 1 関数 GenerateBitMask の引数と返却値の仕様
引数/
返却値
データ型 入力/
出力
説明
Pat[] 文字型 入力 検索文字列が格納されている 1 次元配列 16 ビット
Mask[] 16 ビット
論理型
出力 文字 “A” ~ “Z” に対応するビットマスクが格納される 1 次元配列
返却値 整数型 出力 検索文字列の文字数

  〔プログラム 2 〕

  ○整数型関数: BitapMatch(文字型: Text[], 文字型: Pat[])
  ○16 ビット論理型: Goal, Status, Mask[26]
  ○整数型: i, TextLen, PatLen
  ・TextLen ← Text[] の文字数
  ・PatLen ← GenerateBitMask(Pat[], Mask[])
  ・Status ← "0"B
  ・Goal ← "1"B を (PatLen - 1) ビットだけ論理左シフトした値
  ■ i: 1, i ≦ TextLen, 1
  | ・Status ← Status を 1 ビットだけ論理左シフト値と              fast_rewindα
  |                                         "1"B とのビットごとの論理和
  | ・Status ← Status と Mask[Index(Text[i])] とのビットごとの論理積 fast_rewindβ
  | ▲ Status と Goal とのビットごとの論理積 ≠ "0"B
  | | ・return (i - PatLen + 1)
  | ▼
  ■
  · return (-1)

設問 2 次の記述中の      に入れる正しい答えを,解答群の中から選べ。

 図 1 で示したとおりに, Text[] と Pat[] に値を格納し,関数 BitapMatch を実行した。プログラム 2 の行 β を実行した直後の変数 i と配列要素 Mask[Index(Text[i])]と変数 Status の値の遷移は,表 3 のとおりである。

 例えば,i が 1 のときに行 β を実行した直後の Status の値は “1”B であることから, i が 2 のときに行 α を実行した直後の Status の値は,”1″B を 1 ビッ トだけ論理左シフトした “10” B と “1”B とのビットごとの論理和を取った “11”B となる。次に, i が 2 のときに行 β を実行した直後の Status の値は, Mask[Index(Text[2])] の値が “10101”B であることを考慮すると,   d   となる。

 同様に, i が 8 のときに行 β を実行した直後の Status の値が “10”B であるということに留意すると, i が 9 のときに行 α を実行した直後の行 β で参照する Mask[Index(Text[9])] の値は   e   であるので,行 β を実行した直後の Status の値は   f   となる。

表 3 図 1 の格納例に対してプログラム 2 の行 β を実行した直後の配列要素 Mask[Index(Text[i])] と変数 Status の値の遷移

info右にスクロールします

i 1 2 ・・・ 8 9 ・・・
Mask[Index(Text[i])] “10101”B “10101”B ・・・ “10”B   e   ・・・
Status “1”B   d   ・・・ “10”B   f   ・・・

d ~ f に関する解答群

ア ”0″B  
イ ”1″B  
ウ ”10″B  
エ ”11″B
オ ”100″B 
カ ”101″B  
キ ”10101″B

設問 2 の内容は、問題に示された具体例のデータにおいて、プログラム 2 の β の位置の処理を行った直後に、i と Mask[Index(Text[i])] と Status の値が何になっているかを答えよ、というものです。

ここで、またまた「 Bitap 法なんて知らない!」と怖気づいてはいけません。

擬似言語に示された通りにデータを処理して行けば、空欄を埋められるからです。

 

それでは、トレースしてみましょう。i = 1 ~ 9 までトレースすれば、すべての空欄を埋められます。

トレースするのは、i をループカウンタとした繰り返し処理です。

以下に、プログラムを示します。この短いプログラムを i = 1 ~ 9 までトレースすればよいのですから、決して難しくないはずです。

トレースするのは、β の直後の値であることに注意してください。


  〔プログラム 2 〕

  ○整数型関数: : BitapMatch(文字型: Text[], 文字型: Pat[])
  ○16 ビット論理型: Goal, Status, Mask[26]
  ○整数型: i, TextLen, PatLen
  ・TextLen ← Text[] の文字数
  ・PatLen ← GenerateBitMask(Pat[], Mask[])
  ・Status ← "0"B
  ・Goal ← "1"B を (PatLen - 1) ビットだけ論理左シフトした値
  ■ i: 1, i ≦ TextLen, 1
  | ・Status ← Status を 1 ビットだけ論理左シフト値と              fast_rewindα
  |                                         "1"B とのビットごとの論理和
  | ・Status ← Status と Mask[Index(Text[i])] とのビットごとの論理積  fast_rewindβ
  | ▲ Status と Goal とのビットごとの論理積 ≠ "0"B
  | | ・return (i - PatLen + 1)
  | ▼
  ■
  · return (-1)

トレースした結果を以下に示します。

i Mask[Index(Text[i])] Status
1 “10101”B “1”B
2 “10101”B “1”B(空欄d)
3 “10”B “10”B
4 “101000”B “0”B
5 “101000”B “0”B
6 “10101”B “1”B
7 “10101”B “1”B
8 “10”B “10”B
9 “10101”B(空欄e) “101”B(空欄f)

空欄 d 、空欄 e 、空欄 f の正解は、選択肢イ、選択肢キ、選択肢カです。

秘訣 5:
設問に答えられればよいと割り切って解く

今度は、設問 3 です。問題、設問、解答群を以下に示します。

設問 3

 関数 GenerateBitMask の拡張に関する,次の記述中の      に入れる正しい答えを,解答群の中から選べ。ここで, プログラム 3 中の   b   には,設問 1 の   b   の正しい答えが入っているものとする。

表 4 に示すような正規表現を検索文字列に指定できるように,関数 GenerateBitMask を拡張し,関数 GenerateBitMaskRegex を作成した。

表 4 正規表現
記号 説明
記号 [] 説明 []内に記載されている文字のいずれか 1 文字に一致する文字を表す。例えば, “A[XYZ]B” は, “AXB” , “AYB” , “AZB” を表現している。

  〔プログラム 3 〕

  ○整数型関数: GenerateBitMaskRegex(文字型: Pat[],
                                  16 ビット論理型: Mask[])
  ○整数型: i, OriginalPatLen, PatLen, Mode

  ・OriginalPatLen + Pat[] の文字数
  ・PatLen ← 0
  ・Mode ← 0
  ■ i: 1, i ≦ 26, 1
  | ・Mask[i] ←   b    /* 初期化 */
  ■
  ■ i: 1, i ≦ Original PatLen, 1
  | ▲ Pat[i] = "["
  | | ・Mode 1
  | | ・PatLen ← PatLen + 1
  |--+-----
  | |
  | | ▲ Pat[i] = "]"
  | | | ・Mode ← 0
  | |--+-----
  | | | ▲ Mode = 0
  | | | | ・PatLen ← PatLen + 1
  | | | ▼
  | | | ・Mask[Index(Pat[i])] ← "1"B を (PatLen – 1) ビットだけ
  | | |     論理左シフトした値と Mask[Index(Pat[i])] とのビットごとの論理和
  | | ▼
  | ▼
  ■
  ・return (PatLen)

Pat[] に “AC[BA]A[ABC]A” を格納して,関数 GenerateBitMaskRegex を呼び出した場合を考える。この場合,文字 “A” に対応するビットマスクである Mask[1] は   g   となり,関数 GenerateBitMaskRegex の返却値は   h   となる。また,Pat[] に格納する文字列中において [] を入れ子にすることはできないが,誤って Pat[] に “AC[B[AB]AC]A” を格納して関数 GenerateBitMaskRegex を呼び出した場合, Mask[1] は   i  となる。

g ,i に関する解答群

ア  “1001101”B  
イ  “1010100001”B
ウ  “1011001”B  
エ  “101111”B
オ  “110011”B  
カ  “111101”8

h に関する解答群

ア 4  イ 6  ウ 9  エ 13

「正規表現」という、これまた難しそうな言葉が登場しましたが、決して怖気づかないでください。

どうしてこのプログラムで正規表現に対応できるのかを理解するのではなく、設問に答えられればよいのです。そう割り切って解いてください。

 

プログラムの内容を見て、簡単そうな空欄から解いていきましょう。

まず、PatLen の値を求める空欄 h です。

Mode の初期値は 0 で、Mode = 0 なら 1 文字処理するごとに PatLen の値を 1 増やしています。

“[” を処理すると、PatLen を 1 増やし、Mode を 1 にします。

そして、 “]” を処理すると、Mode を 0 に戻します。

これは、 “[” と “]” で囲まれた部分では、その間に何文字あっても PatLen が 1 だけ増えるということです。

 

したがって、問題に示された “AC[BA]A[ABC]A” という具体例を処理したときの PatLen は、

  1. “AC” で 2 増える
  2. “[BA]” で 1 増える
  3. “A” で 1 増える
  4. “[ABC]” で 1 増える
  5. “A” で 1 増える

全部で 6 になります。

したがって、空欄 h の正解は、選択肢イです。

 

今度は、”A” のビットマスクを求める空欄 g です。

“AC[BA]A[ABC]A” において、
“A” は 5 回登場し、 “[” と “]” で囲まれた部分では、その間に何文字あっても PatLen が 1 だけ増えるのですから、 “ACAAAA” を想定してビットマスクを求めればよいことになります。

“A” は、1 文字目、3 文字目、4 文字目、5 文字目、6 文字目に登場するので、それらの桁位置を 1 とした “111101”B というビットマスクになります。したがって、空欄 g の正解は、選択肢カです。

秘訣 6:
少しぐらいできない問題があっても気にしない

最後は、空欄 i です。

誤って Pat[] に “AC[B[AB]AC]A” が与えられた場合には、
“[B[A” の部分で PatLen が 2 増えてしまうので、 “A” のビットマスクは、”ACBAACA” を想定して求められます。

“A” は、1 文字目、4 文字目、5 文字目、7 文字目に登場するので、それらの桁位置を 1 とした “1011001”B というビットマスクになります。

したがって、空欄 i の正解は、選択肢ウです。

 

この空欄 i は、かなり難しいでしょう。

問題の 60 %以上が正解なら合格なのですから、「少しぐらいできない問題があっても気にしない」でください。

 

最後に、問題の答えをまとめて示しておきます。

解答

設問 1 a – イ b – ア c – ア
設問 2 d – イ e – キ f – カ
設問 3 g – カ h – イ i – ウ

この記事の中で紹介した

「説明文とプログラムを対応付ける」
「問題に示された具体例をヒントにして考える」
「すぐに解けない設問は後回しにする」
「具体例をコツコツとトレースすればできる」
「設問に答えられればよいと割り切って解く」
「少しぐらいできない問題があっても気にしない」

という解法のテクニックと心構えは、午後問題の問 7 ~問 11 のプログラミング言語の問題でも応用できます。

ぜひお試しください。それでは、またお会いしましょう!

 

label 関連タグ
実は、午前試験を『免除』できます 独習ゼミで午前免除試験を受けた 85% の方が、
午前分野を免除しています。
2020年 6月 12日 12時
締め切り間近!!
alarm2020年 6月 12日 12時締切!

詳しく見てみるplay_circle_filled
label これまでの『午後問題の歩き方』の連載一覧 label 著者

『プログラムはなぜ動くのか』(日経BP)が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでPCの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識0ベースのITエンジニアや一般書店フェアなどの一般的なPCユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

  • 「プログラムはなぜ動くのか」(日経BP)
  • 「コンピュータはなぜ動くのか」(日経BP)
  • 「出るとこだけ! 基本情報技術者」 (翔泳社)
  • 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」(翔泳社)
  • 「ifとelseの思考術」(ソフトバンククリエイティブ) など多数