スーパーコンピュータ・コンテスト９７
予選課題

課題説明

つじつま合わせ問題

次の例のように、4 組の 0 と 1 の記号列が与えられていたとする。区別のため、各組の一方の記号列を「青の列」、もう一方を「赤の列」と呼ぶことにする。 

（例）
                  青の列    赤の列
         1 組       010       10
         2 組       101       10
         3 組       0         000
         4 組       0         101

いま、組の番号の列（以下では「組番列」と呼ぶ）を決めると、それに対応す る青の列からなる記号列と赤の列からなる記号列が決まる。たとえば、3, 2, 2 という組番列に対する青の列は 0101101、赤の列は、0001010 である。このよ うに、一般には、青の列と赤の列は異なるが、同じになる場合もある。同じに なった場合に、その組番列を、「つじつまの合った組番列」と呼ぶ。たとえば、 上の例に対しては、次に示すように、2,1,2,1,4,3 が、つじつまの合った組番 列の 1 つになっている。 

                   青の列 = 10101010101000 = 赤の列
与えられた記号列の組に対し、つじつまの合った組番列を求めるのが、「つじ つま合わせ問題」である。

問題

与えられた 4 組の 0 と 1 の記号列に対し、長さが 50 以下で、つじつまの 合った組番列を 1 つ求めるプログラム（Fortran77 または ANSI C言語で）を作成せ よ。（ただし、「長さ」とは、組番列の長さのこと。つまり、使用した組数の こと。たとえば、上の例では組番列が 2,1,2,1,4,3 なので長さは 6 である。） なお、長さ 50 以下で、つじつまの合った組番列が存在しない場合もある。 その場合には、0 を出力させる。

問題の組は、標準入力から与える。このとき、まず、青の列が 4 つ、次に赤 の列が 4 つ与えられるものとする。つまり、上の例は、 

         010  101  0  0  10  10  000  101
と与えられる。記号列間は1個以上の空白とする。（なお、記号列の長さは 5 以下と仮定して良い。）

答えは、標準出力に組番号の列で出力する。ただし、解が存在しないときは 0を出力する。

プログラム中では、Fortran または C 言語で使われている標準的な関数や演 算ならば、何を利用しても構わない。ただし、ビット演算などを使う場合には、 1 ワードが 32 ビットの機械でも動くように（あるいは、そのように修正する ことが簡単なように）、プログラムを作成しておくこと。

評価について

応募プログラムをワークステーション上で、数個の問題例に対して走らせ、そ れぞれ規定時間（1 組あたり 30 秒）以内に正しい答えを出力するかを調べる。 正解数が同じ場合には、短い組番列を出している方を、さらには総計算時間の 少ない方を高く評価する。また、答えの探索方法（レポートにて説明すること） のおもしろさ、ユニークさも評価の対象とする。 なお、評価に際し、使用可能メモリ量の上限は 32MB とする。

(付録)参考例題

参考のため、以下に例を 3 題示す。実際には、この例に類する問題例を数題 用いて評価する。 

問題例1) 101 10 1 0 10 1 100 110
解の例1) 121121211211214144111314424334
         解の長さ 30

問題例2) 101 100 1 0 0 10 001 1
解の例2) 21414124124231423322434431334144224331342422333443
         解の長さ 50

問題例3) 11 10 10 0 00 1 1 011
解の例3) 解は存在せず
         解の長さ 0

応募方法

必要な送付物
  1. 予選課題を解くプログラム　1本

    テキスト形式。

    郵送の場合は、フロッピーディスクに、ファイル名yosen.c(またはyosen.f) という名のプログラムを1本だけ入れて送って下さい。なお、間違いを避け るため、フロッピーディスクには、学校名、チーム名、代表者氏名を書いた ラベルを貼って下さい。

    電子メールで送付する場合は、プログラムの先頭に学校名、チーム名、代表 者氏名を書いたコメント行を入れて下さい。

  2. 実行結果

    実行したマシン名、コンパイラ及び実行結果。

    郵送の場合は、(1)と同じフロッピーディスクにファイル名kekka.txtという 名で入れて下さい。

    電子メールで送付する場合は、先頭に学校名、チーム名、代表者氏名を書い て下さい。

  3. 予選課題解答プログラムの解説

    今回作成したプログラムの考え方、処理方法、工夫した点、などの説明をレ ポート用紙5枚(A4)以内でまとめたもの。 必ず、学校名、チーム名、代表者氏名を書いて下さい。

    電子メールの場合には、標準的なLaTeX、TeXファイルも受け付けます。

    この解説も予選審査の対象となりますので、注意深く、わかりやすく作成し て下さい。

  4. 連絡先

    郵送の場合は、学校名、代表者名、メンバー氏名、7月18日から23日の連絡 先等を明記した紙（応募用紙）を同封して下さい。

    電子メールの場合には、(1)、(2)、(3)は別のメールで、それぞれのメール の最初に、学校名、チーム名、代表者名、メンバー氏名、7月18日から23日 の連絡先を明記して送って下さい。

    予選課題解答プログラムのコンパイル条件などについて質問する場合があり ます。

送付先
締切
電子メール、郵便共、7月17日(木)必着
問い合わせ先