令和元年（R01）秋期 基本情報技術者試験 アルゴリズム問題 解き方解説

令和元年度秋期午後のアルゴリズム問題である問８の私の解き方・考え方について解説していきます。

問題

IPAの公式サイトで公開されています。このページでは問８についての解説を行います。

https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2019h31_2/2019r01a_fe_pm_qs.pdf

問題の概要

作成するプログラムは文字列検索に関するものですが、どちらかというと論理演算（ビット演算）に関する問題と言った方が良さそうです。

スポンサーリンク

設問１

設問１は関数 GenerateBitMask が生成するビットマスクを求める問題と、プログラムの穴埋め問題になります。

関数 GenerateBitMask がどのようなものであるかは [プログラムの説明] の（２）に記載されています。なので、この（２）がしっかり理解できれば設問１は解けます。

ただ（２）の説明は文章として非常分かりにくいので注意が必要です。特に Mask[Index(Pat[i])] が配列の要素番号に関数 Index が組み込まれているのが分かりにくいです。

なので、まず先に関数 Index のみに注目して Index の動きを整理するのが良いと思います。関数 Index の説明は下記のようになっていますが、要は指定された英大文字がアルファベット順で何番目かを取得する関数です。

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

例えば Index(“A”) の返却値は “1”、index(“B” ) の返却値は “2″ といった感じです。なので、図１の Pat[ ] では関数 Index の返却値は下記のようになります。

• i = 1：Index(“A”) = 1
• i = 2：Index(“C”) = 3
• i = 3：Index(“A”) = 1
• i = 4：Index(“B”) = 2
• i = 5：Index(“A”) = 1
• i = 6：Index(“B”) = 2

ここを先に整理しておくと（２）の説明も分かりやすくなると思います。上記を踏まえて（２）に記載された関数 GenerateBitMask を図１の Pat[ ] に関して実行すると、下記のように Mask[ ] に値が格納されていきます。

• Mask [ ] をすべて “0”B で初期化
• i = 1：Mask[1] の下位から１番目のビットの値を１にする
  • Mask[1] が “000000000000000” から “000000000000001” になる
• i = 2：Mask[3] の下位から２番目のビットの値を１にする
  • Mask[3]  が “000000000000000” から “000000000000010” になる
• i = 3：Mask[1] の下位から３番目のビットの値を１にする
  • Mask[1] が “0000000000000001” から “0000000000000101” になる
• i = 4：Mask[2] の下位から４番目のビットの値を１にする
  • Mask[2] が “0000000000000000” から “0000000000001000” になる
• i = 5：Mask[1] の下位から５番目のビットの値を１にする
  • Mask[1] が “0000000000000101” から “0000000000010101” になる
• i = 6：Mask[2] の下位から６番目のビットの値を１にする
  • Mask[2] が “0000000000001000” から “0000000000101000” になる

最終的な Mask[ ] の値は下記になります。

• Mask[1]：”0000000000010101″
• Mask[2]：”0000000000101000″
• Mask[3]：”0000000000000010″

ここで図２を見てみると Mask[1] と Mask[3] の値が上記で求めた結果と一致しているのでここまでの考え方は合ってそうですね！

ここまでが説問１を解くために必要な GenerateBitMask の動きの整理です。

では設問を解いていきましょう。まず [  a  ] で問われているのは Mask[2] の値です。Mask[2] は先ほど求めた通り “0000000000101000” になりますので、[  a  ] の答えは「イ」となります。

次の問題はプログラムの穴埋め問題です。（２）の説明のどの部分がプログラムのどの部分に対応しているかを考えると解きやすいです。

関数 GenerateBitMask は下記の下線の色で分けたように２つの処理から構成されています。１つは青線で示した Mask[ ] の初期化で、もう一つは赤線で示した Mask[ ] への値の設定です。

これらの２つの処理をプログラムに対応させると下のようになります（色で区別してます）。

ですので、[  b  ] が含まれる行は Mask[ ] を “0”B で初期化するため処理であると考えられます。ここで選択肢を見ると、これを実現できそうなのは「ア」のみですね。他の選択肢だと “0”B 以外の値で初期化されてしまいます。ですので、[  b  ] の答えは「ア」となります。

次に [  c  ] について考えます。[  c  ] が含まれる行は（２）の説明の赤下線部を実現する処理となります。つまり、

Mask[Index(Pat[i])]に格納されている値の下位から数えて i ビット目を１にする処理

です。

まずプログラムで出てくる論理和とは、下記のような処理を行う演算です。

２つのビット入力値の一方でも "1" であれば "1" を返却し、両方が "0" の場合のみ "0" を返却する

プログラムの赤枠内ではこの論理和をビット毎に行うようになっていますので、[  c  ] が下位から数えて i ビット目のみ “1” である値であれば、下記を実現する事ができます。つまり [ c ] は下位から数えて i ビット目のみ “1” である値です。

Mask[Index(Pat[i])]に格納されている値の下位から数えて i ビット目を１にする処理

続いて [  c  ] の選択肢を見てみると、「”1″B を〇〇ビットだけ論理左シフト」という言葉が確認できます。論理左シフトとは下記を行う処理になります。

• 指定された値を指定されたビット分左方向にずらす
• ずらすことで右側に空いたビットは “0” で埋める

例えば指定された値が “1”B であるとき、シフト結果は指定されたビット x に応じて下記のようになります。

• x = 0：”0000000000000001″
• x = 1：”0000000000000010″
• x = 2：”0000000000000100″
• x = 3：”0000000000001000″

つまり、下位から数えて （x + 1）番目のビットのみが１となることになります。一方 [  c  ] には、前述の通り下位から数えて i 番目のビットのみが “1” である値が入りますので、シフトするのは「i – 1 ビット」となります。したがって [  c  ] の答えは「ア」となります。

間違えやすいのは「イ」だと思います。ただし「 i ビット」論理左シフトしまうと、シフト結果は下位から数えて「 i + 1」番目のビットが１の値になります。「 Mask[Index(Pat[i])] に格納されている値の下位から数えて i + 1 ビット目を１にする処理」になってしまい、説明と異なった動きになってしまいますので間違いです。

設問２

設問２は [プログラム２] のある時点の変数の値を答える問題になります。

Status ← Status と Mask[Index(Text[i])] のビットごとの論理積

したがって、単純に文章で記載されている Status と Mask[Index(Text[2])] とのビットごとの論理積を求めれば良いだけです。論理積は下記のような処理を行う演算です。

入力された２つのビットの値が両方とも "1" の場合のみ "1" を、それ以外の場合は "0" を返却する

ですので Status には元々の Status と Mask[Index(Text[2])] の両方が “1” であるビットが “1” 、それ以外のビットが “0” である値、つまり “1”B が格納されます。したがって [  d  ] の答えは「イ」となります。

さらに [  e  ] で回答したように、 Mask[Index(Text[9])] は “10101”B ですので、これらの Status と Mask[Index(Text[9])] の値をビットごとに論理積をとった結果は “101”B となります。したがって [  f  ] の答えは「カ」となります。

設問３

設問３は正規表現で検索文字列を指定可能にするための GenerateBitMask を拡張した関数 GenerateBitMaskRegex に関する問題です。

結局は、この関数に検索文字列 Pat[ ] が “AC[BA]A[ABC]A” と “AC[B[AB]AC]A” とした時の Mask[1] と関数の返却値を答える問題ですので、素直に入力値に対してこれらがどのようなものになるかをプログラムを追っていけば解けます。

Pat[ ] が “AC[BA]A[ABC]A” の時に各ループ処理の終了直後の各変数の値の動きを表で表すと下記のようになります。

最終的な Mask[1] と PatLen がそれぞれ [  g  ] と [  h  ] の答えとなります。したがって [  g  ] の答えは「カ」、[  h  ] の答えは「イ」となります。” [ ” から ” ]” までの間は PatLen の値が変化せず、同じビットを “1” とする処理が行われる事が理解できれば、最後まで書き出さなくても回答することは可能だと思います。

また Pat[ ] が “AC[B[AB]AC]A” の時に各ループ処理の終了直後の各変数の値の動きを表で表すと下記のようになります。

最終的な Mask[1] が [  i  ] の答えとなりますので、[  i  ] の答えは「ウ」となります。こちらも ” [ ” から最初の ” ] ” までは PatLen が変化しないことをプログラムから読み取れれば、文字数を数えるだけでも解けてしまう問題だと思います。が、時間があるのであれば各変数の動きを上の表のように地道に追っていった方が無難だと思います。

スポンサーリンク

解いてみた感想

問題をパッと見た感想は「難しい…」でした。特に [プログラム２] は難しいです。なぜあれで文字列の検索ができるのかはいまだに理解できてません。

ですが、実際に問題を解いてみて、難易度は低めだったのではないかと感じてます。理由は変数をトレースするだけで解ける問題が多かったことです。プログラムの穴埋めも少なかったですので、とにかく機械的に変数の動きを追うだけで得点は稼げる問題だったと思います。

今回解いてみて感じたポイントをまとめておきます。

• 問題分が一見難しそうでも解くのは簡単な場合がある（むしろこういうケースは多い）ので、拒絶反応を示さずにじっくり問題を読み解いていく事が重要
• （特に穴埋め問題以外は）プログラムの全体像・全容を理解する必要はない

★オススメページ★
下記ページから他の回の解説もたどれます。他の回のアルゴリズム問題の解き方がわからない場合は是非読んでみてください！

基本情報技術者試験 午後問題「アルゴリズム」過去問の解き方 解説 まとめ

本ページの図・プログラム・問題文について

図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。

出典：令和元年度 秋期 基本情報技術者試験（FE）試験区分 午後 問８

アルゴリズム問題の対策（PR）

過去問を解いてみて感触はいかがだったでしょうか？

全く分からなかった...という方もいらっしゃるかもしれません。はっきりいってアルゴリズム問題は、特に慣れないと難易度は高いです。

なので、こういった方にはもっと "簡単なアルゴリズム問題を解いて慣れていく" ことをオススメします。で、この簡単なアルゴリズム問題を解くのにオススメの本が下記の うかる！ 基本情報技術者　[午後・アルゴリズム編] です。

うかる！ 基本情報技術者　[午後・アルゴリズム編]　2022年版

posted with ヨメレバ

福嶋 宏訓 日経BP 日本経済新聞出版本部 2021年11月25日頃

楽天ブックス

Amazon

Kindle

 

オススメする理由は、特に本の前半部分で難易度の低いアルゴリズムの紹介や解説が行われているところです。こういったアルゴリズムの動作などを実際にトレースして追ってみたりすることで簡単な問題からアルゴリズム問題に慣れていくことができます。

また、「アルゴリズムとは？」といったアルゴリズム入門から解説してくれているので、プログラミングをやったことない方にも親切な内容になっています。

アルゴリズム問題に全く手がつかないというような方は、まずは上記のような本でアルゴリズムに慣れるのがオススメです。

慣れてきたら、あとは実際の過去問を解いて "さらに考える力を養う" ＆ "実際のアルゴリズム問題に慣れる" のが良いと思います。

私のサイトでも過去問の解説をしていますので是非参考にしてください。私の解説だけでなく、他の人の解説も参考にしたいような場合には、下記のような過去問の参考書もオススメです（アルゴリズム問題だけでなく、全問題の解説も充実しています）。

令和04年【上期】基本情報技術者 パーフェクトラーニング過去問題集

posted with ヨメレバ

山本三雄 技術評論社 2021年11月26日頃

楽天ブックス

Amazon

Kindle