プログラミングコンテスト競技部門 - 電気電子工学科

The 17th PSE Workshop’14
プログラミングコンテスト競技部門「キオクのかけらII」に
おける対戦システムの構築準備
The Construction of the Game System in Procon 2014 Competition Section "Find Your PIECE of Mind II"
寺元貴幸1)，松野良信2)，中道義之3)，小嶋徹也4)，後藤弘明5)，鈴木貴樹6)，奥田遼介7)，照井教文8)，
小保方幸次9)，井上泰仁10)，川田重夫11)
Takayuki Teramoto, Yosinobu Matsuno, Yosiyuki Nakamiti, Tesuya Kojima, Hiroaki Goto, Takaki Suzukii,
Okuta Ryousuke, Norifumi Terui, Koji Obokata, Yasuhito Inoue and Shigeo Kawata
1)教授津山高専情報工学科(〒708-8509 津山市沼624-1,Tel. 0868-24-8289, [email protected])
2) 准教授有明高専電子情報工学科(〒836-8585 大牟田市東萩尾町150,Tel. 0944-53-8873, [email protected])
3) 非常勤講師沼津高専 (〒410-8501 沼津市大岡3600,Tel. 055-921-2700, [email protected])
4) 准教授東京高専情報工学科(〒193-0997 八王子市椚田町1220-2,Tel. 0042-668-5111, [email protected])
5) 東北大学大学院情報科学研究科(〒980－8579 仙台市青葉区荒巻字青葉6番3号09, [email protected])
6) 東北大学大学院情報科学研究科(〒980－8579 仙台市青葉区荒巻字青葉6番3号09, [email protected])
7) 東北大学大学院情報科学研究科(〒980－8579 仙台市青葉区荒巻字青葉6番3号09, [email protected])
8) 准教授一関高専物質化学工学科(〒021-8511 一関市萩荘字高梨,Tel. 0191-24-4700, [email protected])
9) 准教授一関高専電気情報工学科(〒021-8511 一関市萩荘字高梨,Tel. 0191-24-4700, [email protected])
10) 講師舞鶴高専電気情報工学科(〒625-8511 京都府舞鶴市字白屋234番地,Tel. 0773-62-8964, [email protected])
11)工博宇都宮大学大学院工学研究科（〒321-8585 栃木県宇都宮市陽東 7-1-2, [email protected]）
The 25th programming contest will be held on October 18 - 19, in Ichinoseki city. We give this paper
about a system construction and use of the competition section of the 25th programming contest. At this
year’s NAPROCK programming contest, the participants compete over puzzles as a team. The
Assignment is a picture which is made of equal-sized pieces. But the pieces are rearranged in random
positions. The participants are required to put the pieces back to the original positions. The assignment
picture is the only reference that the participants will use to estimate the original position of piece.
Key Words: Programming Contest, Puzzle, Image Processing
同士の入れ替えだけで行わなければならない。更に回答
1．はじめに
高専生から一流のプログラマーを育成する目的にプロ
グラミングコンテスト（高専プロコン
1）
時間までの所要時間も重要な要素である．より入れ換え
）が企画され，
操作の少ない回答を，より早く回答したチームが勝利と
今年で25回目の記念大会となる．今年度は一関高専（岩
なる．時間をかけて操作が少ない回答を求めるのか，そ
手県）を主管校として平成26年10月に開催される予定で
れとも操作は多めな回答でも素早く回答するのかが，勝
ある．一関は本来なら平成23年の開催予定地であったが，
負の駆け引きになると考えている．
東日本大震災の影響により開催が急遽変更となった経緯
さらに，今回の競技は勝ち抜け方式で行われる．1試合
がある．今回は震災からの復興へ向けて全国へ多くのメ
を複数の問題で行い，1問ごとに上位チームが勝ち抜け，
ッセージを送る目的もある．
次の試合に進出するなど，いままでの大会では行わなか
高専のプログラミングコンテストは例年通り自由，課
題そして競技の3部門から構成されている．今回のプログ
った運営を行う為，競技システムにもそのための工夫が
必要となる．
ラミングコンテスト・競技部門は1枚の原画像から同サイ
高専プロコンの競技部門は毎年テーマが変更されルー
ズに切り分けられた断片画像をバラバラに並べた問題画
ルだけでなく競技システム全てを刷新している．ここ数
像を元の画像に並べ替えるパズルゲームである．断片画
年競技に関するルールや運用方針の概要は全国プログラ
像の元の位置は問題画像から参加者が推測しなければな
ミングコンテスト委員会がとりまとめ，実際の競技シス
らない．
テムの開発や運用は主管校が主体となって開発を行って
断片画像の並び替えは，第15回（新居浜）大会でもテ
きた．このスタイルは開催地の独自性を生かしたシステ
ーマとして取り上げたが，今回は並び替え方にも工夫が
ム開発が可能なこと，大会前に十分な調整時間をとるこ
必要となる．断片画像の並び替えは，隣り合う断片画像
とができるというメリットがある．反面，開発や運用の
ノウハウが継承されないため，開催地に過度の負担を強
問題画像
いることになった． 2) 3)
・断片画像を無作為に並べ替えた画像である．
今大会においても開催地の高専のOBを中心とした開
発スタッフにより開発が始められた．しかし開発スタッ
フが開催地とは異なった場所にいるため，システムチェ
・断片画像は回転しない．
・並べ替えた断片画像を結合して，原画像と同じサイ
ズの1枚の画像となる．
ックをには万全を期す必要がある．
0
今回もできるだけ多くの参加者に質の高いプログラム
1
2
3
で本選に臨んでもらうよう，あらかじめ練習ができるシ
0
ステムを公開することやルール・アプリケーションのメ
ニューの英語化などできるあらかじめできることは可能
な限り努力している．さらに今回は海外チームが参加す
1
るNAPROCK国際プログラミングコンテストに大学生の
参加も可能としており，更なる混戦が予想される．本稿
では，競技システムの概要について報告する．
(a) 原画像
(b) 問題画像
図１．幅 640 ピクセル，高さ 480 ピクセルの（a）原画像
を，4x2 に分割して作成した(b)問題画像
２．競技概要と競技ルール
今回の競技は1枚の原画像から同サイズに切り分けら
れた断片画像をバラバラに並べた問題画像を元の画像に
選択
並べ替えるパズルゲームである．以下競技で使用する用
・競技者が断片画像の中から1枚の画像を指定するこ
語について説明する．
と．選択した断片画像を選択画像と呼ぶ．
●競技用語
・選択画像は数回変更することが可能だが，回数が制
原画像
限さる．変更回数は問題によって異なり最大16回．
・自然画やイラスト画などのフルカラー画像．
交換
・画像サイズは幅，高さともに最大で1024ピクセル．
・選択画像に隣接する上下左右の4枚の断片画像（選
・問題によって異なる．
択画像の位置によっては3もしくは2枚の場合もあ
分割
る）のうちの1枚と選択画像を入れ替えること．
・原画像を縦，横それぞれ等間隔に分割する．（分割
数は画像サイズの約数になる）
ライン
・同一の選択画像で連続した交換操作．
・分割数は縦，横ともに最大で16である．問題によっ
て異なり，縦と横の分割数が同じとは限らない．
復元
・選択・交換を行い，断片画像を原画像の位置に戻す
断片画像
こと．なお選択・交換で並び替えた画像を復元画像
・原画像を分割して作成した各々の画像．
と呼ぶ．また復元画像と原画像が一致する復元を，
・すべての断片画像のサイズは同じである．
完全復元という．
・断片画像のサイズは幅，高さともに最小で16ピクセ
・原画像によっては同じ断片画像を複数含む場合も
ル，最大で128ピクセルであり，問題によって異な
あり得るが，その場合でもそれぞれの断片画像を原
る．また断片画像の幅と高さは同じとは限らない．
画像の元の位置に戻す必要がある．
断片画像の位置
選択コスト
・断片画像の位置は表１のように左上を00とし，そこ
・選択回数に選択コスト変換レートを掛けた値．選択
から右に順に10，20，30，…，下に順に01，02，03，
コスト変換レートは1以上300以下の整数で，問題に
…とする．
よって異なる．
・断片画像の位置は16進数で表記する．分割は最大16
分割のため位置は00からFFとなる．
交換コスト
・交換回数に交換コスト変換レートを掛けた値．交換
コスト変換レートは1以上100以下の整数で，問題に
表１．断片画像の位置
よって異なる．
00
10
20
…
E0
F0
01
11
21
…
E1
F1
…
…
…
…
…
0E
1E
2E
…
EE
FE
0F
1F
2F
…
EF
FF
時間コスト
・回答を受信するまでの時間（秒数）を100倍した値．
・受信するまでの時間にはフォーマットの検証時間
が含まれる．
・フォーマットの検証時間は5秒程度を予定．回答ご
とに異ならないよう競技サーバー側で統一する．
総コスト
・選択が選択回数に満たない回答や交換が交換回数
・選択コスト，交換コスト，時間コストの合計．
に満たない回答は，フォーマットエラーとする．
有効回答
・その他，フォーマットに合致しない回答はフォーマ
・回答の優先順位を以下のようにし，同一チームが複
ットエラーとする．
数の回答を提出した場合は，最も優先順位の高い回
・特に断らない限り文字コードは UTF-8とし，行は
答のみを有効回答とする．
1.
CR+LFの改行コードで区切られる．
一致断片画像数（原画像との位置が一致した
●勝敗判定
断片画像が多い回答が有効）
1. 一致断片画像数（原画像との位置が一致した断片画
2.
総コスト（総コストの少ない回答が有効）
像が多いチームが上位）
3.
選択コスト（選択回数の少ない回答が有効）
2. 総コスト（総コストの少ないチームが上位）
4.
交換コスト（交換回数の少ない回答が有効）
3. 選択コスト（選択回数の少ないチームが上位）
●問題フォーマット
4. 交換コスト（交換回数の少ないチームが上位）
問題画像はバイナリPPMフォーマットとし，問題ファイ
5. サイコロの目で勝負（サイコロを振って，サイコロ
ルのヘッダ部に次の情報を順にコメントとして記載する．
の目の合計が多いチームが上位）。
・
分割数
●その他のルール等
・
選択可能回数
・競技に持ち込んで利用できるコンピュータ類は，携
・
選択コスト変換レートおよび交換コスト変換レ
帯可能でプログラマブルな装置を3台以内とする．
ート
このうち，少なくとも1台は回答用として，100BASE
ヘッダ部の例を図２に示す．
－ TX が使用可能な RJ45 有線 LAN ポートを有し，
TCP/IP接続可能な装置でなければならない．
・（コンピュータを含む）持ち込み機器間の無線によ
P6
る通信は認めない．
# 4 2 ·········· 分割数
・サーバや他チームの試合進行を妨害する行為は認
# 3 ············ 選択可能回数
めない．
# 150 20 ······· コスト変換レート
640 480 ········ ピクセル数
255 ············ 最大輝度
図２．問題画像ヘッダ部の例
図２は幅640ピクセル，高さ480ピクセルの原画像を
4x2に分割した例で，断片画像のサイズは，幅160ピク
セル，高さ240ピクセルとなる．選択可能回数は3回，
選択コスト変換レートおよび交換コスト変換レートは
それぞれ150および20を示す．ファイル名は問題番号2
桁の前に「prob」を付加して，probXX.ppmとなる．
●回答フォーマット
・ 1行目に選択回数（ライン数）を記録．
３．システム開発状況
競技のルールはそれほど複雑ではないが，質の高いプ
ログラムを作成するには各種の準備が必要である．現在
までに以下の様な作業を行っている．
・平成 25 年 11 月 23 日〜24 日第 1 回競技部会 [一関]
 競技部門の内容の検討
・
・
・
相対位置をU・D・R・L（上・下・右・左）で示す．
・選択回数以上のライン情報が記録された回答は，回
答回数までを回答とみなす．
・交換回数以上の交換操作が記録された回答は，回答
回数までを回答とみなす．
・操作が不可能な回答は，フォーマットエラーとする．
第 3 回競技部会 [ネットミー
平成 26 年 2 月 4 日
第 4 回競技部会 [ネットミーテ
ィング]
 タイトル「記憶のかけら II」の決定．
 募集要項の確認．
 オープン戦（国内の大学生の参加について）につい
・ 1行目に選択する断片画像の位置を記録．
・ 1回の交換操作は，選択画像と交換する断片画像の
平成 26 年 1 月 14 日
 募集要項（原案）の作成，会場の利用計画
に順に記録．
・ 3行目に交換操作を1交換目から順に1行で記録．
第 2 回競技部会 [東京]
ティング]
・ 1つのラインを次のような形式で表し，ラインごと
・ 2行目に交換回数を記録．
平成 25 年 12 月 26 日
 募集要項（原案）の内容検討
ての検討．
・
平成 26 年 2 月 9 日
第 1 回委員会
 募集要項（原案）の提出，勝ち抜け戦の提案
・
平成 26 年 2 月 9 日
第 5 回競技部会 [東京]
 競技部門募集要項の再検討．
・
平成 26 年 4 月 1 日～5 月 16 日
[電子メールで相談]
 質問への回答作成
・
平成 26 年 5 月 31 日
[Web 公開]
競技部門の追加情報の提供
・
FAQ は応募締め切り前で 32 件．
ム勝負であり，他チームの状況が直接自チームに影響を
・
平成 25 年 64 件，平成 24 年 92 件，平成 23 年 3 件，
与えるとこはないため，運の要素は少ないと言える．し
平成 22 年 42 件，21 年度 18 件．
かし，回答のタイミングは非常に重要であり，最適な解
をどの段階で判断するかなど，アルゴリズム以外の要素
４．まとめ
第25回プロコンは1枚の原画像から同サイズに切り分
けられた断片画像をバラバラに並べた問題画像を元の画
像に並べ替えるパズルゲームである．断片画像の元の位
置の推測と，並び換え方法の最適解を探す大きく二つの
も含まれている．海外チームに加えて，大学生も参加可
能になり，より高度なプログラミングが競い合うことと
なる．
運営側はいままでの経験を生かして，なんとか今年の
高専プロコンでも成功を目指したい．
作業が必要となる．
参考文献
断片画像の並び替えは，第15回（新居浜）大会でもテ
ーマとして取り上げたが，今回は並び替え方にも工夫が
必要となる．断片画像の並び替えは，隣り合う断片画像
同士の入れ替えだけで行わなければならない。更に回答
時間までの所要時間も重要な要素である．より入れ換え
1) プログラミングコンテスト公式ホームページ，
http://www.procon.gr.jp/
2) 寺元貴幸,宮下卓也,最上勲,岡田正,井上恭輔,松野良信,
高専教育32, pp. 921-926(2009)
操作の少ない回答を，より早く回答したチームが勝利と
3) 飯田忠夫，田中永美，長岡健一，山田洋士，金寺登:
なる．時間をかけて操作が少ない回答を求めるのか，そ
第13回プログラミングコンテスト競技部門運用支援シ
れとも操作は多めな回答でも素早く回答するのかが，勝
ステムの構築について，高専教育， Vol.27 pp.
負の駆け引きになると考えている．基本的にアルゴリズ
721-726(2004)