アルゴリズム問題こんなもん出来るかと思う問題でも 50 ％以上正解する「 Bitap 法による文字列探索」

矢沢久雄
2022-04-08 更新

この記事は基本情報技術者試験の旧制度（ 2022 年以前）の記事です。
この記事の題材となっている「午後問題」は現在の試験制度では出題されません。ご注意くださいませ。

基本情報技術者試験の受験者の多くは、午後試験のアルゴリズム問題を苦手としています。しかし、その苦手なアルゴリズム問題で、 50 % 以上の正解が得られないと、合格は望めないでしょう。

この連載では、これまでに実施された基本情報技術者試験の過去問題を例にして、最低でも 50 % 正解できる解き方を紹介します。

今回は、現時点で入手できる最新の過去問題である令和元年度秋期「 Bitap 法による文字列探索」を取り上げます。

1 午後試験の配点と合格への戦略
2 「こんな問題わかるか！」と言いたくなるような問題
3 何だかわからなくても説明された通りにやればできる（1）
4 何だかわからなくても説明された通りにやればできる（2）
5 試験問題の解説は、あくまでも参考としましょう

午後試験の配点と合格への戦略

以下は、基本情報技術者試験の午後試験の構成と配点を示したものです。

基本情報技術者試験の午後試験の構成と配点
問題番号	分野	配点
1	情報セキュリティ	20 点
2 ～ 5	ソフトウェア・ハードウェア、データベース、ネットワーク、ソフトウェア設計から 3 問出題マネジメント系、ストラテジ系から 1 問出題	各 15 点
6	データ構造およびアルゴリズム	25 点
7 ～ 11	ソフトウェア開発（ C 言語、Java 、 Python 、アセンブラ言語、表計算ソフトが各 1 問出題）	25 点

問 1 と問 6 は、必須問題です。
問 2 ～問 5 は、 4 問中 2 問を選択します。
問 7 ～問 11 は、 5 問中 1 問を選択します。

100 点満点で 60 点以上（ 60 % 以上の正解）が合格なのですが、苦手なアルゴリズム問題で 60 % 正解するのは至難の業でしょう。前半部の問 1 ～問 5 でガンバって 70 % 正解しましょう。そうすれば、アルゴリズム問題に 50 % 正解で全体で 60 % に達します（ソフトウェア開発でも 50 % 正解してくださいね！）。これが、合格への戦略です。

この連載では、アルゴリズム問題で最低でも 50 % 正解できる解き方を紹介します。

「こんな問題わかるか！」と言いたくなるような問題

令和元年度秋期のアルゴリズム問題（問 8 ）を見てみましょう。以下に、問題と解答へのリンクがありますので、問題にざっと目を通してください。じっくり見ると嫌になっちゃうと思いますので、本当にざっとでいいですよ。

令和元年度秋期基本情報技術者試験午後試験
問題	解答

問題を見たご感想は、いかがですか？「こんな問題わかるか！」と言いたくなるような問題だったでしょう。テーマは、 Bitap 法です。

シラバス（試験の出題テーマの細目を示した資料）にも Bitap 法という用語はありません。強いて言えば、シラバスの「文字列処理のアルゴリズム」という分野に「文字列照合」という用語が示されているので、それで出題されたのでしょう。

ただし、過去の試験に、 Bitap 法が出題されたことはありません。おそらく、これまでに、どんな教材でも、どんな講座でも、 Bitap 法を取り上げているものはないでしょう。 Bitap （ bit-parallel approximate pattern matching 、ビット並列近似パターンマッチング）法は、状態遷移という考え方を使って文字列探索を行うアルゴリズムです。

「こんな問題わかるか！」ですね。

試験には、ときどき「こんな問題わかるか！」と言いたくなるような問題が出ることがあります。そんなときは、頭ごなしに「できない」と決めつけずに、冷静になってください。

アルゴリズム問題は、選択問題ではなく必須問題（受験者の全員が解かなければならない問題）です。もしも、誰もできないような問題を出したら、その年度だけ合格率が極めて低くなってしまいます。それでは、出題者も困るでしょう。そうならないように、この手の問題は「何だかわからなくても説明された通りにやればできる」ようになっています。

何だかわからなくても説明された通りにやればできる（1）

まず、設問 1 の空欄 b がわかりやすいと思いますので、そこから解いていきましょう。以下に、プログラムの説明（該当箇所を抜粋）、プログラム、および空欄 b の解答群を示します。

〔プログラムの説明〕
　関数 GenerateBitMask は， Mask[] の全ての要素を “0”B に初期化した後，

プログラムは横スクロールできます

〔プログラム〕

○整数型関数 : 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)

〔解答群〕

b に関する解答群

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

プログラムの説明とプログラム（ご丁寧にも /* 初期化 */ というコメントまであります）を対応付けると、空欄 b で行われている処理が

Mask[] の全ての要素を “0”B に初期化

だとわかるでしょう。空欄 b の解答群を見ると、選択肢アの “0”B が適切です。何だかわからなくても説明された通りに（プログラムの説明の通りに）やって、正解を選べました。同様の解き方で、空欄 c と空欄 a も正解を選べるでしょう。

何だかわからなくても説明された通りにやればできる（2）

今度は、設問 2 です。これは、以下のプログラムで、 Mask[Index(Text[i])] と Status の値をトレース（処理の流れと変数の変化を追いかけること）せよ、という問題です。

これこそ正に、何だかわからなくても説明された通りに（プログラムの内容の通りに）やればできる、の好例です。プログラムの意味も、何をやっているかも、わからなくて構いません。

Mask[Index(Text[i])] の初期値を “10101”B とし、
Status の初期値を “1”B として
トレースすればよいのです。

〔プログラム〕

○整数型関数: 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)

以下は、プログラムをトレースした結果です。これによって、空欄 d 、空欄 e 、空欄 f の正解を選べます。

プログラムをトレースした結果
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 ）

さあ、これで十分でしょう。

この問題には、設問 1 （ a 、 b 、 c ）、設問 2 （ d 、 e 、 f ）、設問 3 （ g 、 h 、 i ）という、全部で 9 つの選択項目がありますが、ここまでで 6 つに正解できました。それぞれの配点はわかりませんが（設問ごとの配点は公開されていません）、 9 つの内の 6 つに正解できたのですから、きっと 50 % に達したでしょう。

設問 3 は、正規表現という、これまた小難しそうなテーマをからめているので、できなくても気にしないでください。