第１回「ＫＬＩＣプログラミング・コンテスト」
規定課題

［課題］

ある放送局がいくつかのプレゼント企画をしました。

それぞれ多くの応募があり、中には一つのプレゼント企画に対して一人で 複数の応募をしている応募者もいます。

この放送局は応募者に電話番号を記入させることで、応募の整理をしやす くしています。この電話番号で応募者は一意に決まるものとしましょう。一人 が家族の名前を使って複数応募した場合や、同じ家庭から数人が応募した場合 は、電話番号で整理しているのですべて同一人物の複数応募とみなされてしま いますが、これは構わないことにします。

この応募者のリストはプレゼントの賞品の抽選に用いることはもちろんで すが、どの家庭がどの賞品に興味を持ったかを知ることで、今後の賞品の選定 やマーケティングなどにも役立てることができます。

ここでは簡単のため、電話番号は数字１桁からなるとします。

例えば、プレゼント A に応募した人の電話番号をそれぞれ 7, 1, 2, 7, 7としましょう。7 の電話番号を持つ人は 3 通も応募しています。

一方、プレゼント B に応募した人の電話番号は 5, 7, 2, 7 だとしましょ う。

この状況は、{7,1,2,7,7} というマルチ集合 A と、{5,7,2,7} というマ ルチ集合 B で表現することができます。なおマルチ集合では、要素の順序に 意味がありません。ですから {7,1,2,7,7} も {2,1,7,7,7} も {7,2,7,1,7} なども全て同じマルチ集合 A を表したものとみなされます。

さて、このようなデータに以下のようなマルチ集合の演算を施すと、そこ から様々な情報を読み取ることができます。以下に、いろいろな演算とその例 を示します。

Union:

プレゼント A とプレゼント B は別企画だが共通で抽選を行なう賞品があ るので、両プレゼントの応募全体を求めたい。上の A と B の例を使って式で 表すと、

{7,1,2,7,7}∪{5,7,2,7} ＝ {7,7,2,7,7,5,1,7,2}

となります。

Contraction:

ある賞品の抽選に当たっては同一人の複数の応募をひとつと見なしたい。

Contraction の操作を単項演算子↓で表すと次のようになります。

↓{7,1,2,7,7} ＝ {2,1,7}
↓{5,7,2,7} ＝ {5,7,2}

Intersection:

プレゼント A とプレゼント B の両方に応募しているのは誰か？　両方に 複数応募しているのなら、それはそれだけ熱心に両方を欲しているのだから、 何重に応募しているのかも知りたい。

{7,1,2,7,7}∩{5,7,2,7} ＝ {7,2,7}

Difference:

プレゼント B よりプレゼント A を誰がどれくらい強く欲しているのかを 知りたい。具体的には、誰がプレゼント A にプレゼント B より何通多くの応 募を出したのか、ということになります。また、その逆はどうなっているのか も知りたい。Difference の操作を二項演算子 ＼ で表すと次のようになりま す。

{7,1,2,7,7}＼{5,7,2,7} ＝ {7,1}
{5,7,2,7}＼{7,1,2,7,7} ＝ {5}

ではいよいよ、課題の本体です。

マルチ集合の演算に関して次の 7 つの述語を持つモジュール multi_set のプログラムを作成して下さい。

１　 あるマルチ集合がリスト表現 L で与えられた時、それを適当な内部 表現 M　 に変換する述語: encode(L, M)

２　 逆に内部表現 M からリスト表現 L に戻す述語: decode(M, L)

３　 内部表現で与えられたマルチ集合 M0, M1 の和集合 M0 ∪ M1 = M を計算する述語: union(M0, M1, M)

４　 同様に積集合 M0 ∩ M1 = M を計算する述語: intersection(M0, M1, M)

５　 差集合 M0 ＼ M1 = M を計算する述語: difference(M0, M1, M)

６　 マルチ集合 M0 中の同一要素の重複を取り除いた集合 M を計算する 述語: contraction(M0, M)

７　 マルチ集合 M から適当な要素を 1 つ取り出し、その要素 E(整数) と残り のマルチ集合 S(内部表現) を返す述語: choose(M, E, S) (ただし M ＝ φの場合を考慮 する必要はない)

AITEC で用意した審査用プログラムを使って、 1, 2 のエンコード/デコー ドのプログラムと、 3-7 の演算プログラムを適宜呼び出して走行テストを行 い、正しい答えを計算するかどうかチェックします。

本課題で最初に審査用プログラムから与えられるマルチ集合のデータは、 重複しているかも知れない整数を要素として持つリストとして表されています。

今回、このマルチ集合の要素は整数に限定します。一方、応募者のプログ ラムは、このリスト表現のデータを各自のフォーマットに変換して保持/演算 を行なうことが出来ます。そして最終的な答えは再びリスト表現に戻されます。

この走行テストのイメージを掴んで頂くために、最後に審査用プログラム の例を添付しますが、実際の審査では、これとは異なる審査用プログラムを使 用しますので予めご了承下さい。実際にデコーダ/エンコーダ、演算プログラ ムに与えられるマルチ集合のサイズはかなり大きくする予定です。また illegal な入力に対する処理はプログラムしなくても OK です。つまり、1 に 関して L はリスト表現であることを、 2-7 に関して M、 M0、 M1 は正しい 内部表現のマルチ集合であることを仮定して構いません。

並行並列プログラミングの醍醐味は「非常にバラエティに富んだ現実の実 行状況を想定して、 いかに美しくて効率の良いプログラムを書くことができ るか」と言っても過言ではありません。 応募者は、そのバラエティに富んだ 実行状況を各自でいろいろ想定して上記の 7 つの述語のプログラムに取り組 んでみて下さい。並行並列プログラミングにおいては、良いプログラムの基準 は一通りではありません。審査プロセスには、審査委員が応募作品のソースコー ドを読んで判断する作業も含まれています。

簡単でも良いですから、応募者は何故そのようなプログラミングをしたのかと いう考察を作品のプログラムに添付して下さい。