www.youtube.com 今回の動画では、平成30年度 秋期 応用情報技術者試験 午後問3（プログラミング）を取り上げ、DNA配列のような長大な文字列を効率的に解析するためのデータ構造である「ウェーブレット木（Wavelet Tree）」を用いたアルゴリズムについて詳しく解説します。本問は、一見すると高度で難解なテーマに見えますが、出題の本質は「ビット列を使ってデータを段階的に振り分ける」という基本的な考え方と、その処理を正確にプログラムで表現できるかどうかにあります。午後試験のプログラミング問題としては、データ構造の理解とビット演算の実装力の両方が試される、差がつきやすい良問です。 問題文では、DNA配列を例に、複数種類の文字が混在する長い文字列に対して、特定の文字がどの位置に何回出現するかを高速に求める仕組みが示されています。ここで用いられるウェーブレット木は、文字を数値に符号化し、そのビット列を上位ビットから順に見て、0なら左、1なら右という規則でデータを分割していく再帰的な構造を持っています。出題趣旨としては、この構造を正しく理解し、木の構築過程と探索過程の双方を追えるかどうかが重視されています。 設問1では、与えられた文字列をどのように符号化し、各ノードでどのビットを参照して左右に振り分けるのかを理解しているかが問われます。特に重要なのは、「どの深さでは、どのビット位置を見るのか」という対応関係です。深さが1増えるごとに、参照するビット位置も1つずれていくというルールを正確に把握できていないと、キー値や部分文字列の導出でつまずいてしまいます。ここでは計算自体よりも、構造を頭の中で正しくトレースできるかどうかが合否を分けるポイントになります。 設問2では、各ノードにおける文字の出現回数と、ビット0と1による分岐の関係が問われます。ウェーブレット木では、各ノードが保持するビット列によって、次の探索範囲が決定されます。ビット0が左の子ノード、ビット1が右の子ノードに対応しており、現在注目している区間の中で、どれだけの要素が次の階層に進むのかを正確に数えられるかが重要です。ここを感覚的に処理してしまうと、後続の設問3で致命的なミスにつながります。 設問3は本問最大の山場であり、rank関数のプログラム穴埋めを通じて、ビット演算の理解が直接的に問われます。特定のビット位置の値を取り出すために、ビットシフトと論理積（AND）を組み合わせる定石的な処理が登場し、DEPTH と現在の深さ d からシフト量を導出するロジックを正確に書けるかどうかが鍵になります。また、次の探索対象となる文字列長を count で更新していく流れは、ウェーブレット木の探索アルゴリズムそのものを反映しており、単なるコード暗記では対応できません。問題文と擬似コードを照らし合わせながら、一行ずつ処理の意味を追えるかどうかが、ここでの得点を大きく左右します。 設問4では、計算量とメモリ量の評価が問われます。各ノードで行っている処理自体は定数時間であっても、木の高さが文字種の数 σ に対して対数オーダーで増加することから、全体の計算量は log₂(σ) に依存する形になります。この「一段あたりは軽いが、段数が増える」という感覚を持てているかどうかが、計算量評価の正確さにつながります。午後試験では、オーダー記法を形式的に書くだけでなく、その意味を理解しているかが見られている点にも注意が必要です。 この問題全体を通しての難所は、ウェーブレット木という新しいデータ構造に気後れせず、「ビットによる振り分け」と「範囲の更新」という二つの基本操作に分解して考えられるかどうかにあります。設計思想を理解できれば、ビット演算の処理も、単なるテクニックではなく必然的な実装として納得できるようになります。本動画では、問題文に沿って木の構築から探索、そして計算量評価までを一貫した流れで解説しており、アルゴリズム分野やC言語系のビット操作に苦手意識がある方でも理解しやすい構成になっています。プログラミング問題を得点源にしたい方や、高度なデータ構造の考え方を体系的に整理したい方は、ぜひ最後まで視聴して合格への力を確実なものにしてください。
