高専プロコン28競技部門 都立(品川)
第28回高専プロコン(コレ)の競技部門に都立産技高専(品川)から参加しました！
これで高専プロコンの参加は4回目になります。過去の体験記(第26回)はこちらです。
hokekyo1210.hatenablog.jp
結果
今年の結果は優勝でした！
全試合で単独満点を達成することが出来たのは本当に嬉しかったです。
さらに、本校は3年連続で賞を受賞しています(競技部門としては初らしい)。
開発メンバーは以下の４人です。
- はたの (1年)
- @w_yasu_w0809 (3年)
- @Mahito6 (5年)
- @_hokekyo1210 (5年)
そもそも高専プロコン
全国で55校ほどある高等専門学校(いわゆる高専)から、それぞれ1チームずつが参加するプログラミングの大会です。
高専プロコンは3つの部門に分かれていますが、今回受賞した競技部門は、特定の問題に対する解答用プログラムを事前に用意して、大会当日に競わせる競技形式の大会です。
競技部門を簡単にまとめると以下のようになります。
- 準備期間は半年
- チームでの開発が可能
- 厳密解を求められない問題が多い
- ハードウェアを工夫しなければいけない問題が多い
今年の問題
今年の競技部門は、バラバラに切断された「木製のピース」と「ピースがぴったりハマる枠」が与えられて、そのパズルを好きな方法で解けという問題でした。
実はこれ、問題の概要は去年とまったく変更されていません(細かい部分は変更されています)。2年連続でまったく似た問題が出題されるのは、過去の高専プロコンには無かったと思います。
このようになってしまった理由は様々な場所で議論されている気がするので、改めて言及はしません。気になる人はぜひ調べてみましょう。
今年の問題の特徴は以下のようになります。
- パズルが完成しない場合、得点は0点
- ピースの個数は最大で50個
- ピースおよび枠の頂点は必ず格子状の点に乗る(つまり整数座標のみでパズルを表現できる)
- パズルの枠はA4のスキャナに収まる
- 試合中にはコンセントが使用できる
- 持ち込むPCの台数に制限はない
- 減点されるが、ピースおよび枠の形状情報をヒントとして得ることも出来る
基本方針
今年のパズルは、数十分程度では人力で解くことが出来ないよう工夫されており、プログラムの介入は必要不可欠でした。
基本的には、ピースと枠をどうにかしてプログラムが理解できるデータとして表現する必要があります。これには2種類の方法があり、「減点覚悟でヒントを用いる」もしくは「スキャナやカメラを用いてピースと枠の頂点情報を抽出する」となります。前者はQRコードを入力する機構を用意すれば良いだけなのに対して、後者は適切な画像処理を組む必要があるなど、難易度が高いということが言えます。
僕らのチームは、「ヒントを用いないチームはいても2，3チーム程度だろう」という希望的観測と、「前回大会の画像処理ノウハウを用いれば、他チームを上回る精度は出せるだろう」という自信から後者を選択しました。
最終的な方針は以下のようになりました。
- A4スキャナを用いてピースと枠をスキャン
- 画像処理を用いてデータ化
- ビームサーチと呼ばれる探索アルゴリズムでパズルを解く
- ソフトウェアのアシスト付きで、2人がかりでピースを埋める
ピースや枠の画像処理は必ずしも正しいデータを求められる保証が無かったため、いくつか誤ったピースがあってもそれっぽい解を出せる探索アルゴリズムとして、ビームサーチを選択しました。決勝の問題などでも、誤って検出したピースがいくつかあったため、この選択は正しかったと思います。
4年間の総評
競技部門めっちゃ楽しかったです！これからはOBとして大会にちょっかい出すと思います。競技勢がこれを読んでモチベーション上げてくれたら嬉しいなあ。
