「何色? サッと見 発見伝」
競技部門概略
第20回プログラミングコンテスト・競技部門は、数色のパネルが配置されたマス目状に区切られたフィールド上で、その一部の領域を回転しながら、色ごとに連続した領域にまとめるパズルゲームです。いかに少ない回転数で完成状態にできるかを競います。
パズルのルール
- 図1「初期状態」に示すような、色付きのマス目(セルと呼びます)が並べられたフィールドが問題として示されます。
- 競技者はフィールドの一部の正方形の領域を回転させることを繰り返して、縦横に連結した同一色の領域(クラスタと呼びます)を大きくします。
- 1回の回転(ステップと呼びます)ではn×n(nは正の偶数)の領域を、その領域の中心に対して点対称に90度単位で90?270度回転させることができます。図2に4×4の領域を270度右に回転した例を示します。
- 目標の状態は、図1「完成状態」に示すような、各色が1つのクラスタにまとまった配置です。クラスタの条件を満足していれば形は問いませんので、図に示した以外にも完成状態の配置は多数存在します。
- 初期状態から完成状態にするまでのステップ数を競います。


競技手順
- 競技開始と同時に3つの問題が、ネットワーク経由で公開されます。
- 各チームは制限時間内(10?15分程度を予定、競技開始前までに指定します)に、3問すべてを解き、解答(回転手順)をネットワーク経由で提出します。なお、完成状態にならない解答でも提出できます。
- 各チームから提出された解答手順を再演して、試合の順位を判定します。
勝敗判定
勝敗の判定は、まず各問題毎の順位を決め、それらを集計して試合全体の順位を決定します。なお、同じ問題に複数回の解答が提出された場合は、最後に提出された解答とその提出時間を用いて勝敗の判定をおこないます。
各問題の順位は次の優先度で決定します。
- 各色の最大クラスタのサイズ(セル数)を合計した数の大きいチーム(完成状態では、この最大クラスタサイズ合計値がフィールド中の全セル数に等しくなります)
- 項目1が同じ場合はステップ数が少ないチーム
試合全体の順位は、次の優先度で決定します。
- 順位の合計が小さいチーム
- 項目1が同じ場合は、問題Aでの順位が高いチーム
- 項目2が同じ場合は、問題Bでの順位が高いチーム
- 項目3が同じ場合は、問題Cでの順位が高いチーム
- 項目4が同じ場合は、問題Aで解答の提出された時間の早いチーム
- 項目5が同じ場合は、問題Bで解答の提出された時間の早いチーム
- 項目6が同じ場合は、問題Cで解答の提出された時間の早いチーム
- 項目7で決まらない場合はじゃんけん
クラスタについて
クラスタは、同色のセルが上下左右の1か所以上で接続された連続するセルの領域です。したがって、1つ以上の同色のセルからクラスタが構成されることになります。また、完成状態に至っていない状態では、同色のクラスタが複数存在することになります。
複数の同色のクラスタが存在する場合は、クラスタに含まれるセルの数(クラスタのサイズ)が最大のもの1つのみが勝敗判定に使われます。
出題される問題
各試合では、問題A,B,Cの3つの問題を出題します。各問題のフィールドは1辺が5から20の大きさの正方形です(縦、横の大きさは必ず同じです)。一つの問題に使われる色は8色以下です。
その他のルールと注意事項
- 各試合では全チームが同じ問題に取り組み、勝敗を競います。
- 利用できるコンピュータ類は携帯可能なものを2台以内とします。そのうち少なくとも1台は100BASE-TXが使用できるEthernetポートとUSBポートを持つ必要があります。コンピュータは用意されたテーブルに置くものとします。
- テーブルには150W程度の1口の電源コンセントを用意する予定です。
- 競技中は、チーム内での情報のやり取りは構いませんが、チーム以外と情報交換することは認めません。
- 無線LANの利用は認めません。
- 他チームの試合進行を妨害する行為は認めません。
- 試合の進行の妨害や審判または他チーム等への妨害、その他禁止行為があったと判断された場合等には、失格とすることもあります。失格とした場合は、試合の順位は最下位となります。
- 提出された解答手順のデータに誤り(ルール上許されない回転を指示しているなど)がある場合、または制限時間内に解答が提出されなかった場合は、その問題についての順位は最下位となります。
- ネットワークによる問題の配信と解答の提出について、主催者側のシステムに不具合が発生した場合はUSBフラッシュメモリ等のオフラインでの問題の配布と解答の提出になることがあります。この場合、解答提出時間による順位の判定は行いません。
- 主催者側にトラブル等があった場合は、別の問題を用意して再試合を実施する可能性があります。
問い合わせについて
問い合わせは、プロコン公式サイトで指定された「問い合わせ先」へお願いします。問い合わせの回答は逐次プロコン公式サイトに公開します。質問は公開されることを念頭においてください。競技の勝敗を左右するようなアイデアでも公表します。
問い合わせ締め切り : 平成21年5月15日(金) 17:00まで
※問い合わせの際は、所属(高専名・学生の場合は学科学年・教員の場合は所属学科など)と名前を、必ず明記してください。所属や名前が記載されていない場合は、回答できないこともあります。
※ 締め切り後に届いた質問に関しては回答できません。