Last Updated : 11, Jul, 2005
SuperCon 2005
予選問題解答

予選審査において,次の9個のデータ
000000000100000000012
00000001000000012
0110111101111011110012
1010101101101101011010110112
11101010101010101112
11112
1110011100111001110010012
0010110000001011000010110010112
01010101011110002
を使いプレテストを行い,25チーム中19チームがパスし,ついで10万件のランダム データによって時間を測定しました.上位10チームは1秒以下で正解を出し,残りの チームは正解を出すまでに16秒から数十秒の時間を要し(この段階で答えを出したり 出さなかったり不安定なプログラムが1件あり),明らかに有意の差がありこの結果を 元に本選出場10チームを選びました.

予選問題の解答(ソースコード)を掲載いたします。 なお、このプログラムは基本的な解法を説明するもので,10万件データに 関しても70秒程度の時間がかかり,本選には出場できません.

今回の予選課題「最長繰り返し区間探索問題」は一見, パズルのように見えますが,実は,以下のような背景があります.

近年、ヒトをはじめとする様々な生物においてDNA配列が 解読されているが、これらの膨大なデータを解析するには 計算機を用いることは必須となっている。 そういった計算機による重要なDNA配列解析のひとつに タンデムリピート検出というものがある。タンデムリピート とは、DNA配列上でほぼ同じ塩基列が繰り返し現れるような 構造で、遺伝子の重要なひとつの構造であるともいわれ、また この繰り返しの数によって個人を特定できたりもするなど 非常に重要なゲノム上の特徴である。 DNAの配列には4種類の塩基が含まれるが、簡単のため 塩基数を2種類に限定した問題が今回の問題である。 なお、実際のタンデムリピートにおいては、繰り返しが 類似はしていても完全に一致しないことも多いが、今回の 課題ではそれについては考慮していない。

この問題は長さnの入力文字列に対して最悪でもO(n log n) の計算量で解くことが可能である。ここで、O(n log n)とは 適当な定数k,cが存在して、n>kなるすべてのnに対して計算時間 がcn log n以下になる、という意味である。

この問題をこの計算量で解くには、接尾辞木と呼ばれるデータ 構造を用いるとよいことが知られている。接尾辞木は、 文字列中の部分文字列を効率的に検索することができる 索引構造の一つである。このデータ構造を用いると、さらに 追加のデータ構造が必要ではあるが、ある文字列中の 2つの位置から始まる部分文字列がどれくらいの長さで一致する かを定数時間で計算することができることが知られている。 このデータ構造と、さらにクイックソートなどでも有名な 分割統治のテクニックを組み合わせることでO(n log n)を 実現することができる。 なお、接尾辞木ではなく、それを簡略化した接尾辞配列という データ構造を用いても同様の計算を行うこともできる。 なお、ここで述べた接尾辞木、接尾辞配列の研究はここ数年で飛躍的に 進歩しており、情報科学的にも極めてホットな話題である。

(この解法を説明した内容と,プログラムを近日中に公開いたします)

Global Scientific Information and Computing Center
Global Scientific Information and Computing Center,Tokyo Institute Of Technology ++supercon@gsic.titech.ac.jp++