全宇宙生命ゲノムデータベース (Problem E, 2006 Japan Domestic)

ICPC国内予選が終わりました。順位表と問題セットが公開されています。

この順位表によると，4問以上解けたチームは210チーム中たったの12チーム。これらのチームが解いた問題はおそらくABDEでしょう（5問解けた2チームがCとFのどちらを解いたのかは気になります）。実力があるにも関わらず3問しか解けなかったチームの多くは解く問題の選定を間違えたのかと思いますが，多くは次の2ケースではないでしょうか：

今回最も難しかったCとFに（間違って）挑戦してしまった
Eの簡単な解法が分からずに挑戦してはまった

ICPCは「はまってしまうかどうか」がかなり鍵となると思います。チーム全体で解法（アルゴリズム）やソースコードをピアレビューしてはまらないように気をつけるのが重要なのですが，これが意外と難しくてはまってしまいます。ええ，私のチームもそうでした，うむむ。

今回は4問が解けていたら（時間/ペナルティが高くても）確実に国内予選は突破できたので，その鍵となるE問題 "全宇宙生命ゲノムデータベース" の解説を行います。この問題は（動的計画法の問題にも通ずるところがありますが）解法が思いつくかどうかが勝負の分かれ目でしょう。

さて，問題を読むとこれは一種の構文解析の問題であることが分かります。解析自体は文字列をごりごりいじればいいので困ることはないでしょう。

この問題を最初にざっと読むと思いつくのが「ああ，単純に計算結果の文字列を展開してバッファに埋め込んでいけばいいのかな」という解法なのですが，サンプル入力の4番目を見るとこの作戦はうまくいかないことが分かります。ちなみにサンプル入力の4番目とは次の入力です：

1000(1000(1000(1000(1000(1000(NM)))))) 999999

明らかに $1000^6 = 10^{18}$ のバッファを確保することはできませんし埋め込むために計算することもできません。文字列を展開せずに求めるインデックスの値を出力可能な他のアルゴリズム（とデータ構造）を考える必要があります。

解法としては色々と考えられます。

例えば，元々の「結果の文字列を展開する」というアイデアから，文字列をバッファに埋め込まずに「繰り返しの内側の長さ」を求め，長さ×繰り返し回数が求めるインデックスを超えるか超えないかを判定し，インデックスを超えていなければ次の要素に進み，超えていればその繰り返し構造の中の「インデックス mod 繰り返し回数」（インデックスを繰り返し回数で割った余り）番目が答えであることが分かります。

ですから，多重の繰り返し構造がある場合は，多重繰り返し構造の一番内側から計算していけば（長さがlong intを超えずに）求めるインデックスがどの繰り返し構造にあるのかが分かるので，後はその繰り返し構造内でインデックス番目の文字を求めればいいことになります。実際にこの問題はこれで解けるはずです（少なくともサンプル入力は通る）。しかし，このアルゴリズムは次の3ステップがあって複雑です：

入力文字列をパースして内部データ構造に変換する
どの繰り返し構造内に解のインデックスがあるかを特定する（再帰関数）
特定した繰り返し構造内でインデックスにある文字を探す（再帰関数）

上記では「内部データ構造」を説明していませんでしたが，複雑な処理をする場合はいったん生データ（今回は文字列）を操作に便利なデータ構造（例えばリストやスタック，グラフなど）に変換してしまった方がすっきりします。

さて，実際にはこの問題はもっと簡単に解けます（これが出題者の意図していた解法でしょう）。その解法は「実際に繰り返し回数分forループを回せばいい」ということに基づきます。具体的なアルゴリズムは以下の通りです（求めるインデックスを index とする）：

入力文字列をパースしてリスト構造を作る
次の再帰関数にリストの先頭を渡す：
1. a) 文字ノードなら index を1減らす
2. b) 繰り返しノードなら繰り返し回数分その子ノードに対して再帰関数を呼ぶ
3. 次のノードがあればそれについて上記a)b)を調べる

リスト構造は，1番目と3番目のサンプル入力に対してそれぞれ次のリストを作るようにすればよいでしょう。

いつもと違ってC++でプログラムを記述すると次のようになります：

int index;
char answer;

struct node {
  int type;    // 0 = 文字ノード, 1 = 繰り返しノード
  node *next;  // 次のノード; なければNULL

  // 文字ノードのデータ
  char c;      // 文字

  // 繰り返しノードのデータ
  int repeat;  // 繰り返し回数
  node *child; // 繰り返し構造内の先頭ノード
};

void rec(node *n) {
  if (answer != '0') return;

  while (n) { // 終端ノードに達するまで
    if (n->type == 1) { // 文字ノード
      if (index == 0) { answer = n->c; return; }
      index--;
    } else if (n->type == 2) { // 繰り返しノード
      for (int i=0; i<n->repeat; i++) { rec(n->child); }
    }
    n = n->next;
  }
}

int main() {
  string input;

  while(cin >> input >> index, (in != "0" || n)) {
    // リスト構造に変換して先頭ノードを返す
    node *head = parse(input);

    answer = '0';
    rec(head);
    cout << answer << endl;
    
    // メモリを解放
    // free_list(head);
  }
  
  return 0;
}

解答プログラムそのものを載せるのが目的ではないので，parse関数などについては書きません。リスト構造を作るプログラムは少し長くなりますが，そのおかげで実際に解を求める部分はたかだか十数行に収まっています。

今回は（問題が簡単なので）短いですが以上です。国内予選に落ちた方は今回を踏まえて来年に向けて，国内予選を突破した方は11月のアジア地区予選に向けて練習に励みましょう！