山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

令和元年 (2019) 秋期 基本情報技術者試験 問8 アルゴリズム

基本情報技術者試験

www.jitec.ipa.go.jp

普段競技プログラミングアルゴリズムの問題を解いているので、基本情報のアルゴリズムの問題も解いてみました。まあ、資格自体は取得済なんですが。

問8 Bitap 法

設問1

a. イ

対応する文字の Mask の下位から数えて i 番目のビットを 1 にするので、ACABAB の B に対応するビットマスクは、"101000" となるので、イが答えとなります。

b. ア

関数 GenerateBitMask は、Mask の全ての要素を "0"Bに初期化するので、アとなります。

c. ア

i 番目のビットを 1 にしたいので、 2^{i - 1}Masl[Index(Pat[i])] との論理和を取ります。

例えば、1 番目のビットを 1 にしたいときは、1 と論理和を取り、2番目のビットを 1 にしたいときは、2 と論理和を取るので、(i -1) ビットだけ論理左シフトした値となります。

設問2

α がやっていることは、"001101" というビットを "011011" とするように、全てのビットを左に一つ動かし、最下位のビットを 1 にします。

d. イ

"11"B と "10101"B の論理積なので、"1" となります。

e. キ

Text[9] = A なので、A のビットマスクは "10101"B となります。

f. カ

"101"B と "10101"B の論理積なので、"101"B となります。

設問3

g. カ

"AC[BA]A[ABC]A" を "A" について注目すると、"ACAAAA" となるので、Mask[1] は "111101"B となります。

h. イ

の中の文字数に依らず、PatLen の長さは 1 しか増えないので、"AC[BA]A[ABC]A" の長さは 6 となります。

i. ウ

"AC[B[AB]AC]A" はまず、"AC" で "01"B が確定します。次に、[B で "001"B となります。次に、[AB で "1001"B となります。"[AB" の "B" でマスクのビット列が増えない理由は、このとき Mode = 1 なので、PatLen の長さが増加していないからです。 次に、"]A" で "11001"B となり、"C]A" で "1011001" B となります。

感想

ビットを利用したアルゴリズム競技プログラミングでも出てくるので、やっていることは何となく分かりました。

情報処理教科書 出るとこだけ! 基本情報技術者 テキスト&問題集 2019年版

情報処理教科書 出るとこだけ! 基本情報技術者 テキスト&問題集 2019年版

  • 作者:矢沢 久雄
  • 出版社/メーカー: 翔泳社
  • 発売日: 2018/11/28
  • メディア: 単行本(ソフトカバー)