令和元年 (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 となります。